关于链表的一道题，求大神教教！！

Question

给你一个链表L和一个链表P，它们包含已升序排列的整数。操作printLots(L,P)将打印L中那些由P所指定的位置的元素。例如P = 1,3,4,6.那么L中的第1个，第三个，第四个，第六个将会被打印出来。

从《数据结构与算法分析》中看到的。下面是我的代码，顺便请各位大大批评纠正。。我要疯了。

    public void printLot(ListNode a,ListNode b)
    {
        int count = 0;
        int index = 0;
        m = new ListNode(0);
        while(a.next != null)
        {
            if(count == index)
            {
                m = m.next;
                m.element = a.element;
                b = b.next;
                index = b.element;
            }
            a = a.next;
            count++;
        }
    }

Answer 1

伪代码：

// Get K-th element of List 
NodeType getKElement(List L , int k )
{
    ...
}

// Main 
int main(){
Node* p = P ; 
while ( p != NULL ){
  print getKElement(L , p->value) ; 
  p = p->next ; 
}
}

上面的最好理解了

因为P是已经排好序的 ， 所以你也可以每次从上次的地方向下找 ， 复杂度从 $ O(n^2) $ 变为 $ O(n)$ 。

Answer 2

public static void printLot1(LinkList a, LinkList b) {
    Link tempB = b.getFirst();
    while (tempB != null) {
        int count = tempB.dData;// b中元素,对应a中的下标
        Link tempA = a.getFirst();
        int index = 0;//扫描到a的第几个元素
        while (tempA != null) {
            if (count == index) {
                System.out.println(tempA.dData + " ");
                break;
            }
            index++;
            tempA = tempA.next;
        }

        tempB = tempB.next;
    }
}

O(n^2)

Answer 3

struct Node{
    Node* next;
    int data;
};

void print(Node* a,Node* b){
    if(a==NULL||b==NULL) return;
    int before=1;
    while(b!=NULL){
        int data=b->data;
        //需要移动的步数
        int step=data-before;
        while(step--){
            a=a->next;
            //data大于a的表长度
            if(a==NULL)
                break;
        }
        if(a!=NULL){
            printf("%d\n",a->data);
            before=data;
        }else
            break;
         b=b->next;
    }
}