java - 关于链表的一道题，求大神教教！！-PHP中国語ネットワークQ&A

記事特集学ぶダウンロードに質問プログラミング辞典ゲーム最近の更新

简体中文(ZH-CN) English(EN) 繁体中文(ZH-TW) 日本語(JA) 한국어(KO) Melayu(MS) Français(FR) Deutsch(DE)

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

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

283

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

返信を追加