java - 关于链表的一道题，求大神教教！！-PHP中文网问答

文章专题 AI工具学习下载问答源码最近更新

PHP

会员中心讲师中心微信公众号

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

迷茫 2017-04-17 11:05:58

[Java讨论组]

329

给你一个链表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++;
        }
    }

迷茫

业精于勤，荒于嬉;行成于思，毁于随。

全部回复(3)

阿神2017-04-17 11:07:58 3楼

伪代码：


// 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)$ 。

赞 +0

添加回复

巴扎黑2017-04-17 11:07:58 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)

赞 +0

添加回复

巴扎黑2017-04-17 11:07:58 1楼

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;
    }
}

赞 +0

添加回复

专题推荐

更多>

热门话题

热门教程

更多>