當(dāng)前位置：首頁(yè) > 编程资源 > 编程问答 >内容正文

编程问答

链表面试笔试题目总结

發(fā)布時(shí)間：2023/12/10 编程问答 27 豆豆

生活随笔收集整理的這篇文章主要介紹了链表面试笔试题目总结小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)，凡是學(xué)計(jì)算機(jī)的必須的掌握的，在面試的時(shí)候經(jīng)常被問(wèn)到，關(guān)于鏈表的實(shí)現(xiàn)，百度一下就知道了。在此可以討論一下與鏈表相關(guān)的練習(xí)題。

1、在單鏈表上插入一個(gè)元素，要求時(shí)間復(fù)雜度為O(1)

解答：一般情況在鏈表中插入一元素是在末尾插入的，這樣需要從頭遍歷一次鏈表，找到末尾，時(shí)間為O(n)。要在O(1)時(shí)間插入一個(gè)新節(jié)點(diǎn)，可以考慮每次在頭節(jié)點(diǎn)后面插入，即每次插入的節(jié)點(diǎn)成為鏈表的第一個(gè)節(jié)點(diǎn)。

2、給定一個(gè)鏈表，判斷是否有環(huán)。

解答：這個(gè)是一個(gè)經(jīng)典的問(wèn)題了，思路也很簡(jiǎn)單，我們首先設(shè)置兩個(gè)指針p1，p2同時(shí)指向鏈表的頭部，然后p1每次向后走1步，p2每次向后走2步。如果有環(huán)，那么有一步會(huì)出現(xiàn)p1=p2，如果p2已經(jīng)到達(dá)了尾結(jié)點(diǎn)，則無(wú)環(huán)。復(fù)雜度：時(shí)間：O(n)，空間：O(1)

擴(kuò)展：給定一個(gè)鏈表，找出環(huán)的入口位置。思路也是一樣，用p1,p2指針。只是需要多做一步，那就是當(dāng)p1=p2的時(shí)候，將p1重新指向鏈表的頭結(jié)點(diǎn)，然后p1和p2都每次向后走一步，下一次p1=p2的結(jié)點(diǎn)就是環(huán)的入口。復(fù)雜度：時(shí)間：O(n)，空間：O(1)

3、遍歷單鏈表一次，找出鏈表中間節(jié)點(diǎn)

解答：定義兩個(gè)指針p和q，初始都指向鏈表頭節(jié)點(diǎn)。然后開(kāi)始向后遍歷，p每次移動(dòng)2步，q移動(dòng)一步，當(dāng)p到達(dá)末尾的時(shí)候，p正好到達(dá)了中間位置。

4、單鏈表逆置，不允許額外分配存儲(chǔ)空間，不允許遞歸，可以使用臨時(shí)變量，執(zhí)行時(shí)間為O(n)

解答：這個(gè)題目在面試筆試中經(jīng)常碰到，基本思想上將指針逆置。如下圖所示：

實(shí)現(xiàn)：

Node* reverse_list(Node *head){Node *cur=head;Node *pre = NULL;Node *post = cur->next; <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// Node *reverse_head = cur;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(post){cur->next = pre;pre = cur;cur = post;post = post->next;}cur->next = pre; <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// reverse_head = cur;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return cur; }

擴(kuò)展：鏈表翻轉(zhuǎn)。給出一個(gè)鏈表和一個(gè)數(shù)k，比如，鏈表為1→2→3→4→5→6，k=2，則翻轉(zhuǎn)后2→1→6→5→4→3，若k=3，翻轉(zhuǎn)后3→2→1→6→5→4，若k=4，翻轉(zhuǎn)后4→3→2→1→6→5，用程序?qū)崿F(xiàn)。

實(shí)質(zhì)是也是逆置，只不過(guò)是兩個(gè)鏈表逆置后再串聯(lián)起來(lái)。實(shí)現(xiàn)如下：

<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">bool <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">rotate_list<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(Node *head,<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int k,Node* &newhead){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(k < <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">false;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">if<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(0 == k)return <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">true;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int len = <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0;Node *node=head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(node){++len;node = node->next;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(k > len)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">false;Node *one_end,*two_start;node = head;Node *post = node->next;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int n=k;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1 == n){}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(n > <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1){<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// rotate sublist onenode->next = post->next;post->next = head;head = post;post = node->next;--n;}}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(len-k <= <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1){ <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// rotate sublist two}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{one_end = node;node = post;post = post->next;two_start = node;n = len-k;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(n><span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1){one_end->next = post;node->next = post->next;post->next = two_start;two_start = post;post = node->next;--n;}}newhead = head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">true; }

5、用一個(gè)單鏈表L實(shí)現(xiàn)一個(gè)棧，要求push和pop的操作時(shí)間為O(1)

解答：根據(jù)棧中元素先進(jìn)后出的特點(diǎn)，可以在鏈表的頭部進(jìn)行插入和刪除操作

6、用一個(gè)單鏈表L實(shí)現(xiàn)一個(gè)隊(duì)列，要求enqueue和dequeue的操作時(shí)間為O(1)

解答：隊(duì)列中的元素是先進(jìn)先出，在單鏈表結(jié)構(gòu)中增加一個(gè)尾指針，數(shù)據(jù)從尾部入隊(duì)，從頭

部入隊(duì)。

7、給定兩個(gè)鏈表（無(wú)環(huán)），判斷是否有相交。

解答：首先明確一點(diǎn)，如果兩個(gè)鏈表相交，那么從第一個(gè)交點(diǎn)開(kāi)始到尾結(jié)點(diǎn)結(jié)束，所有的結(jié)點(diǎn)都是公共結(jié)點(diǎn)。所以，兩個(gè)有公共結(jié)點(diǎn)而部分重合的鏈表，拓?fù)湫螤羁雌饋?lái)像一個(gè)Y，而不可能像X。

這也就是說(shuō)，如果兩個(gè)鏈表相交，那么這兩個(gè)鏈表的尾結(jié)點(diǎn)肯定是公共結(jié)點(diǎn)，如果尾結(jié)點(diǎn)不是公共結(jié)點(diǎn)，那么這兩個(gè)鏈表肯定不相交。

所以我們可以如下操作：依次遍歷兩個(gè)鏈表，最后判斷尾結(jié)點(diǎn)是否相同，如果相同，則相交，如果不相同，則不相交。復(fù)雜度：時(shí)間：O(m+n)，空間：O(1)

或者一個(gè)鏈表的頭結(jié)點(diǎn)指向另一個(gè)鏈表的尾節(jié)點(diǎn)，判斷是否有環(huán)。

8、給定兩個(gè)鏈表（無(wú)環(huán)），找到第一個(gè)公共節(jié)點(diǎn)。

解答：我們最容易想到的是從尾結(jié)點(diǎn)開(kāi)始挨個(gè)向前比較，最后一個(gè)相同的就是第一個(gè)公共結(jié)點(diǎn)。（從后往前遍歷）

但是單鏈表只能從前往后進(jìn)行遍歷，如果想要從后往前的話則需要先從前向后遍歷一次，同時(shí)用棧來(lái)記錄每一個(gè)結(jié)點(diǎn)，最后出棧，然后挨個(gè)對(duì)比，這樣的確可行，但是卻要額外付出O(m+n)的空間，時(shí)間復(fù)雜度O(mn)。（單鏈表+棧）

仔細(xì)想想，我們可以先分別遍歷兩個(gè)單鏈表，記錄長(zhǎng)度m和n（無(wú)妨假設(shè)m>n），然后先讓長(zhǎng)度為m的鏈表向后走(m-n)步，接著兩個(gè)鏈表同時(shí)向后遍歷，第一個(gè)相同的結(jié)點(diǎn)就是要求的第一個(gè)公共結(jié)點(diǎn)。復(fù)雜度：O(m+n)m,n分別為兩個(gè)鏈表的長(zhǎng)度；空間：O(1)

PS：另外還有一種巧妙的方法是把在一個(gè)鏈表尾部插入另一個(gè)鏈表，然后判斷合成的新鏈表是否有環(huán)。環(huán)入口即為第一個(gè)公共點(diǎn)。

可參考：http://www.voidcn.com/blog/wcyoot/article/p-2762597.html

擴(kuò)展：兩個(gè)鏈表，找出他們的第一個(gè)交點(diǎn)，要求每個(gè)鏈表只能遍歷一次，可以對(duì)鏈表進(jìn)行任何操作，空間O(1).

題目告訴說(shuō)可以對(duì)鏈表進(jìn)行任何操作，這是一個(gè)沒(méi)有用到的條件（大家一定要注意到題目中沒(méi)有用到的條件，往往是解題的關(guān)鍵所在）。

1.遍歷第一個(gè)鏈表List1，將每一個(gè)節(jié)點(diǎn)的next都置為NULL。

2.遍歷第二個(gè)鏈表List2，List2的尾節(jié)點(diǎn)就是第一個(gè)交點(diǎn)。

9、?給定2個(gè)鏈表，求這2個(gè)鏈表的并集(鏈表)和交集(鏈表)。不要求并集(鏈表)和交集(鏈表)中的元素有序。輸入：List1:10->15->4->20，List2:8->4->2->10輸出：交集(鏈表)：4->10；并集(鏈表)：2->8->20->4->15->10

法一：簡(jiǎn)單直觀的方法：

InterSection(list1,list2):初始化結(jié)果鏈表為空，遍歷鏈表1，在鏈表2中查找它的每一元素，如果鏈表2中也有這個(gè)元素，則將該元素插入到結(jié)果鏈表中。

? ? ?Union(list1,list2): 初始化結(jié)果鏈表為空，將鏈表1中的所有元素都插入到結(jié)果鏈表中。遍歷鏈表2，如果結(jié)果鏈表中沒(méi)有該元素，則插入，否則跳過(guò)該元素。

法二：可適應(yīng)歸并排序，not clear。

法三：Hash法

Union(list1,list2)，首先用鏈表1初始化結(jié)果鏈表，創(chuàng)建一個(gè)空的hash表。遍歷鏈表1，將鏈表中的元素插入到hash表。然后遍歷list2，對(duì)于list2中的元素，如果hash表中不存在該元素，則同時(shí)將該元素插入到結(jié)果鏈表中，如果hash表中已經(jīng)存在，則忽略該元素，繼續(xù)遍歷下一個(gè)元素。

InterSection(list1,list2)，首先初始化結(jié)果鏈表為NULL，創(chuàng)建一個(gè)空的hash表。遍歷list1，將list1中的每一個(gè)元素都插入到hash表中。然后遍歷list2，對(duì)于list2中的元素，如果已經(jīng)存在于hash表中，則將該元素插入到結(jié)果鏈表，如果不存在與hash表中，則忽略該元素，繼續(xù)遍歷下一個(gè)元素。

參考：http://blog.csdn.net/lalor/article/details/7430631

10、從單鏈表返回倒數(shù)第n個(gè)元素

普通，基本思路就是用棧，一一壓棧，再?gòu)棗?#xff0c;第n個(gè)元素就可出來(lái)。

進(jìn)階，看到棧，就應(yīng)該想到遞歸，遞歸是天然的棧。用全局變量，實(shí)現(xiàn)如下：

Node* pn_elem = NULL; <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int nn; <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">void <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">recursive<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(Node* node){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(!node) <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return ;recursive(node->next);<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1==nn) pn_elem = node;--nn; }

高級(jí)，維護(hù)兩個(gè)指針，兩個(gè)指針相差n個(gè)元素，當(dāng)前面的指針到達(dá)鏈表末尾，后面指針?biāo)傅脑丶词撬蟮脑?。?shí)現(xiàn)如下

Node* last_n_elem(Node*node,<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int n){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(node! || n<<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1) returnNULL;Node *p=node,*q=node;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(n><span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0 && q){q=q->next;--n;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(q){q=q->next;p=p->next;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return p; }

11、鏈表元素去重，從未排序的鏈表中移除重復(fù)的項(xiàng)。

思路：可使用額外的空間的話，可以用數(shù)組存數(shù)字，實(shí)現(xiàn)最好的方式就是哈希表啦。遍歷一下即可。

實(shí)現(xiàn)：

std::<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">map<Node*, <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">bool>hash; <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">void <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">duplicate_remove<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(Node *node){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(!node) <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return ;Node *post=node->next;hash[node->data] = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">true;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(post){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(hash[post->data]){Node *temp = post;post = post->next;node->next = post;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">delete temp;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{hash[post->data] = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">true;node = post;post = post->next;}} }

如果不允許使用臨時(shí)緩存，怎么解決？

思路：用兩個(gè)指針。當(dāng)某個(gè)指針指向某個(gè)元素時(shí)，另一個(gè)指針將后面的相同元素全部刪除。復(fù)雜度O(n^2)。具體實(shí)現(xiàn)就不寫(xiě)了。

12、鏈表求和問(wèn)題。

該問(wèn)題基本上有兩個(gè)類型：

a、1->2->5->4 , 2->5->3->4,得3->7->8->8.

思路：先加高位，再加低位。兩個(gè)0~9的數(shù)相加，要么不進(jìn)位，要么進(jìn)位為1.用兩個(gè)指針，p指向當(dāng)前進(jìn)位點(diǎn)，q指向當(dāng)前操作點(diǎn)。當(dāng)然第一個(gè)元素得特殊考慮，可能進(jìn)位嘛。

自己實(shí)現(xiàn)：

Node* merge_list_add(Node *list1,Node *list2){Node*q1=list1,*q2=list2,*ans=NULL,*pre=NULL,*p=NULL,*q=NULL;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int cvalue = q1->data+ q2->data;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">bool flag = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">false;ans = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// node 1<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(cvalue ><span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">9){ <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//進(jìn)位pre = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();pre->data =cvalue%<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;ans->next = pre;ans->data = <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;p=pre;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">if<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(9 == cvalue){<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//最高位為9flag = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">true;ans->data =cvalue;pre= ans;p=pre;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{ans->data =cvalue;p = pre= ans;}q1=q1->next;q2=q2->next;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(q1 && q2){<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// the following nodeq = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();pre->next = q;cvalue = q1->data+ q2->data;q->data =cvalue%<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(cvalue > <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">9 ){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(flag){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(p != ans){p->data += <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//999...[],前面全是9Node*temp = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();temp->data= <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;temp->next= ans;flag =<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">false;ans =temp;p = ans;}}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{p->data +=<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">for(p=p->next;p!=q;p=p->next){p->data =<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0;}}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">if<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(cvalue <9){p = q;}pre = q;q1=q1->next;q2=q2->next;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return ans; }

參考：http://hawstein.com/posts/add-singly-linked-list.html,第二種實(shí)現(xiàn)不錯(cuò)

b、元素個(gè)數(shù)不一定相同，高位在后，個(gè)位在鏈表頭結(jié)點(diǎn)。1->2->3 ,?4->5->3->4，得5->7->6->4.

思路：需要注意的是，鏈表為空，有進(jìn)位，鏈表長(zhǎng)度不一樣。

<span class="hljs-preprocessor" style="border: 0px; margin: 0px; padding: 0px; font-weight: bold; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(153, 153, 153); background: transparent;">#<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">include <assert.h> <span class="hljs-preprocessor" style="border: 0px; margin: 0px; padding: 0px; font-weight: bold; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(153, 153, 153); background: transparent;">#<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">include <iostream> <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">using <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">namespace <span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">std; <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">struct Node{<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int data;Node *next; }; Node* create_list(<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int arr[],<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int len){assert(arr &&len><span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0);Node *head = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();head->data = arr[<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0];Node *cur=NULL;Node *pre=head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">for(<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int i=<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;i<len;++i){cur = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node();cur->data =arr[i];pre->next = cur;pre = cur;}cur->next = NULL;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return head; } Node* merge_list_add(Node *list1,Node *list2){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(NULL == list1) returnlist2;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(NULL == list2) returnlist1;Node *ans=NULL,*pre=NULL;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int c=<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0;<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//進(jìn)位<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int value = <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(list1 &&list2){value =list1->data +list2->data + c;Node* temp = newNode();temp->data =value%<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;c = value/<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(pre){pre->next =temp;pre = temp;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">elseans=pre=temp;list2 = list2->next;list1 =list1->next;} <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(!list1 &&!list2 && c><span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0){<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//兩個(gè)鏈表長(zhǎng)度一樣，但有進(jìn)位Node* temp = newNode();temp->data = <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1;temp->next =NULL;<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//結(jié)束pre->next = temp;}<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//有一個(gè)鏈表更長(zhǎng)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(list1){value =list1->data + c;Node* temp = newNode();temp->data =value%<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;c = value/<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;pre->next = temp;pre = temp;list1 =list1->next; }<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(list2){value =list2->data + c;Node* temp = newNode();temp->data =value%<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;c = value/<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">10;pre->next = temp;pre = temp;list2 =list2->next; }pre->next = NULL;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return ans; } <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">main<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int a[]={<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">2,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">7};<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int b[]={<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">4,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">5,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">3,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">9,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">3};<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//此處應(yīng)該加個(gè)判斷，保證數(shù)組元素均在[0,9]Node* lista =create_list(a,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">3);Node* listb =create_list(b,<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">5);Node* cur = lista;<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">"list a:";<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(cur != NULL){<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<cur->data<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">"";cur = cur->next;}cur = listb;<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<endl<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">"listb: ";<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(cur != NULL){<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<cur->data<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">"";cur = cur->next;}<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<endl;Node *ans =merge_list_add(lista, listb);<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">for(; ans; ans=ans->next)<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<ans->data<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">" ";<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<endl; }

13、用算法實(shí)現(xiàn)刪除鏈表的一個(gè)中間節(jié)點(diǎn)，所知的只有該節(jié)點(diǎn)的指針。如a-b-c-d-e中只知道c的指針，實(shí)現(xiàn)a-b-d-e。

思路：若直接刪除的話，鏈表就斷了，可是無(wú)法得到節(jié)點(diǎn)c的前驅(qū)b。故可轉(zhuǎn)換思路利用c的后繼d。將d的值賦給c，然后將后繼節(jié)點(diǎn)d刪除，也就實(shí)現(xiàn)刪除操作。

由于c的位置不定，得分情況討論。一、c為普通的中間節(jié)點(diǎn)，用上述方式解決。二，c為頭節(jié)點(diǎn)，用上述方式解決。三、c為尾節(jié)點(diǎn)，一般認(rèn)為刪除即可，但是會(huì)出現(xiàn)問(wèn)題。刪除之后，尾節(jié)點(diǎn)的前驅(qū)不為空，下次遍歷就會(huì)出錯(cuò)，特別注意。四、c為空節(jié)點(diǎn)，直接返回。

實(shí)現(xiàn)：

擴(kuò)展：

a、Google題目，給定單向鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，定義一個(gè)函數(shù)在O(1)時(shí)間刪除該結(jié)點(diǎn)。

思路跟前面的一致，同樣要注意尾節(jié)點(diǎn)。

b、只給定單鏈表中某個(gè)結(jié)點(diǎn)p(非空結(jié)點(diǎn))，在p前面插入一個(gè)結(jié)點(diǎn)。

思路：首先分配一個(gè)結(jié)點(diǎn)q，將q插入在p后，接下來(lái)將p中的數(shù)據(jù)copy入q中，
然后再將要插入的數(shù)據(jù)記錄在p中。

14、環(huán)鏈表開(kāi)始節(jié)點(diǎn)，1->2->5->4->2

思路：

1、????????用快慢指針，滿指針1，快指針2。

我們注意到第一次相遇時(shí)，指針走過(guò)的路程S1 = 非環(huán)部分長(zhǎng)度 + 弧A長(zhǎng)

快指針走過(guò)的路程S2 = 非環(huán)部分長(zhǎng)度 + n * 環(huán)長(zhǎng) + 弧A長(zhǎng)

S1 * 2 = S2，可得非環(huán)部分長(zhǎng)度 = n * 環(huán)長(zhǎng) - 弧A長(zhǎng)

讓指針1到起始點(diǎn)后，走過(guò)一個(gè)非環(huán)部分長(zhǎng)度，指針2過(guò)了相等的長(zhǎng)度。

就是n * 環(huán)長(zhǎng) - 弧A長(zhǎng)，正好回到環(huán)的開(kāi)頭。

或者參考：http://blog.csdn.net/lalor/article/details/7628332

?2、 ? ? 更簡(jiǎn)單直觀的方法就是利用哈希表。無(wú)環(huán)的話，每個(gè)地址就是不一樣；有環(huán)的話，兩個(gè)地址一樣的就是環(huán)開(kāi)始節(jié)點(diǎn)。下面用c++的map實(shí)現(xiàn)

std::map<Node*, bool>hash;

Node* loop_start(Node* node){

? while(node){

? ??? if(hash(node))?

????????? return node;

????? else{

????????? hash(node) = true;

????????? node = node->next;

????? }

? }

? return NULL; //return head ;??same

}

15、如何知道環(huán)的長(zhǎng)度

一、在環(huán)上相遇后，記錄第一次相遇點(diǎn)為pos，之后指針slow繼續(xù)每次走1步，fast每次走2步。在下次相遇的時(shí)候fast比slow正好又多走了一圈，也就是多走的距離等于環(huán)長(zhǎng)。

　　設(shè)從第一次相遇到第二次相遇，設(shè)slow走了len步，則fast走了2*len步，相遇時(shí)多走了一圈：環(huán)長(zhǎng)=2*len-len。

二、利用哈希表，即兩個(gè)碰撞元素間的個(gè)數(shù)

16、輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)打印出每個(gè)結(jié)點(diǎn)的值。

思路：用棧實(shí)現(xiàn)。

進(jìn)階：用遞歸。實(shí)現(xiàn)如下：

注意：但使用遞歸就意味著可能發(fā)生棧溢出的風(fēng)險(xiǎn)，尤其是鏈表非常長(zhǎng)的時(shí)候。所以，基于循環(huán)實(shí)現(xiàn)的棧的魯棒性要好一些。

17、輸入兩個(gè)遞增鏈表，合并為一個(gè)遞增鏈表。

思路：遍歷兩個(gè)鏈表，依次比較，形成新的隊(duì)列

進(jìn)階：遞歸，每次遞歸返回合并后新鏈表的頭結(jié)點(diǎn)

list_node*List::recursive_merge(list_node * a,list_node * b){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(a == NULL)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return b;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(b == NULL)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return a;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(a->value <= b->value){a->next=recursive_merge(a->next,b);<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return a;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(a->value > b->value){b->next=recursive_merge(a,b->next);<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return b;} }

18、用鏈表實(shí)現(xiàn)約瑟夫環(huán)

這里就不實(shí)現(xiàn)了。

19、判斷一條單向鏈表是不是“回文”，1-2-4-2-1

思路：對(duì)于單鏈表結(jié)構(gòu)，可以用兩個(gè)指針從兩端或者中間遍歷并判斷對(duì)應(yīng)字符是否相等。但這里的關(guān)鍵就是如何朝兩個(gè)方向遍歷。

由于單鏈表是單向的，所以要向兩個(gè)方向遍歷的話，可以采取經(jīng)典的快慢指針的方法，即定位到鏈表的中間位置，再將鏈表的后半逆置，最后用兩個(gè)指針同時(shí)從鏈表頭部和中間開(kāi)始同時(shí)遍歷并比較即可。

實(shí)現(xiàn)：（注意鏈表元素的奇偶性，稍微不同）

20、從尾到頭輸出鏈表。

題目：輸入一個(gè)鏈表的頭結(jié)點(diǎn)，從尾到頭反過(guò)來(lái)輸出每個(gè)結(jié)點(diǎn)的值。

思路：跟輸出倒數(shù)第n個(gè)元素的方法類似。

方法一、先把鏈表反向，然后再?gòu)念^到尾遍歷一遍。但該方法需要額外的操作

方法二、設(shè)一個(gè)棧，從頭到尾遍歷一次，把結(jié)點(diǎn)值壓力棧中，再出棧打印。

方法三、遞歸。

實(shí)現(xiàn)：

擴(kuò)展：該題還有兩個(gè)常見(jiàn)的變體：

1. 從尾到頭輸出一個(gè)字符串；

2. 定義一個(gè)函數(shù)求字符串的長(zhǎng)度，要求該函數(shù)體內(nèi)不能聲明任何變量。

兩個(gè)的分別實(shí)現(xiàn)：

<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">void <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">reverseString<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(conststring& s,<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">unsigned <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int begin){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(!s.size())<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(begin>=s.size())<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return;reverseString(s,begin+<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1);<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">cout<<s[begin]<<<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">" "; }
<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">getLength<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">const <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">char *s){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(*s==<span class="hljs-string" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(33, 145, 97); background: transparent;">'/0')<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">0;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return getLength(s+<span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1) + <span class="hljs-number" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(64, 160, 112); background: transparent;">1; }

21、鏈表和數(shù)組的區(qū)別？

分析：主要在基本概念上的理解。但是最好能考慮的全面一點(diǎn)，現(xiàn)在公司招人的競(jìng)爭(zhēng)可能就在細(xì)節(jié)上產(chǎn)生，誰(shuí)比較仔細(xì)，誰(shuí)獲勝的機(jī)會(huì)就大。

數(shù)組無(wú)需初始化，因?yàn)閿?shù)組的元素在內(nèi)存的棧區(qū)，系統(tǒng)自動(dòng)申請(qǐng)空間。而鏈表的結(jié)點(diǎn)元素在內(nèi)存的堆區(qū)，每個(gè)元素須手動(dòng)申請(qǐng)空間，如malloc。也就是說(shuō)數(shù)組是靜態(tài)分配內(nèi)存，而鏈表是動(dòng)態(tài)分配內(nèi)存。鏈表如此麻煩為何還要用鏈表呢？數(shù)組不能完全代替鏈表嗎？回到這個(gè)問(wèn)題只需想想我們當(dāng)初是怎么完成學(xué)生信息管理系統(tǒng)的。為何那時(shí)候要用鏈表？因?yàn)閷W(xué)生管理系統(tǒng)中的插入，刪除等操作都很靈活，而數(shù)組則大小固定，也無(wú)法靈活高效的插入，刪除。

數(shù)組是線性結(jié)構(gòu)，靜態(tài)分配內(nèi)存，在內(nèi)存中連續(xù)，數(shù)組元素在棧區(qū)?？梢灾苯铀饕?#xff0c;時(shí)間復(fù)雜度O(1)。數(shù)組插入或刪除元素比較困難，時(shí)間復(fù)雜度O(n)。

鏈表也是線性結(jié)構(gòu)，動(dòng)態(tài)分配內(nèi)存，在內(nèi)存中不連續(xù)，鏈表元素在堆區(qū)。元素的定位均需遍歷，時(shí)間復(fù)雜度O(n)。鏈表插入或刪除元素操作靈活性強(qiáng)，時(shí)間復(fù)雜度O(1)。

22、編寫(xiě)實(shí)現(xiàn)鏈表排序的一種算法。說(shuō)明為什么你會(huì)選擇用這樣的方法？

思路：如果只是數(shù)據(jù)內(nèi)容之間的相互交換，那么這種排序方法也比較適合鏈表的排序，插入、冒泡、希爾和選擇排序?？焖倥判颉⒑喜⑴判颉⒍雅判蚨忌婕暗搅酥虚g值的選取問(wèn)題，所以不大適合鏈表排序。

選擇排序的實(shí)現(xiàn)：

Node* insert_sort(Node *head){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(!head ||!head->next)<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return head;Node *p,*q,*pre,*temp;p=head->next;head->next=NULL;<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// p is the head of unsorted list<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// head is the head of sorted list<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(p){q=head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(q &&(q->data < p->data)){pre=q;q=q->next;}temp = p->next;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(q==head){p->next = q;head = p;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">else{pre->next=p;p->next = q;}p=temp;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return head; }

其他排序參考：http://www.voidcn.com/blog/Hackbuteer1/article/p-999842.html

http://wenku.baidu.com/link?url=CxhR7E5PGrEwRU5eKu_3xX5EvZ6MP-7GhRLhAfoQFThh5HxlQ5SgIxdfRPVXRO-oeCkwFYFqLJJezeswxdOmRE4W_QJBY3iS4Xpot23XCPi

23、復(fù)雜鏈表的復(fù)制（默認(rèn)無(wú)環(huán)）

Q:有一個(gè)復(fù)雜鏈表，其結(jié)點(diǎn)除了有一個(gè)m_pNext指針指向下一個(gè)結(jié)點(diǎn)外，還有一個(gè)m_pSibling指向鏈表中的任一結(jié)點(diǎn)或者NULL。請(qǐng)完成函數(shù)ComplexNode* Clone(ComplexNode* pHead)，以復(fù)制一個(gè)復(fù)雜鏈表。

一開(kāi)始想這道題毫無(wú)思路，如果蠻來(lái)，首先創(chuàng)建好正常的鏈表，然后考慮sibling這個(gè)分量，則需要O(n^2)的時(shí)間復(fù)雜度。

思路一：一般復(fù)制一個(gè)簡(jiǎn)單鏈表就這么遍歷一遍就好了，這個(gè)復(fù)雜鏈表，比簡(jiǎn)單鏈表多的地方就在于多了一個(gè)sibling的指針，也就是說(shuō)在建立完簡(jiǎn)單鏈表之后，如何在新的鏈表中找到sibling對(duì)應(yīng)的地址。我們已知的是舊的節(jié)點(diǎn)的地址，所以只需要用一個(gè)map，保存每一個(gè)節(jié)點(diǎn)舊的節(jié)點(diǎn)對(duì)應(yīng)的新的節(jié)點(diǎn)的地址即可。（即將原鏈表中的結(jié)點(diǎn)N和相應(yīng)復(fù)制結(jié)點(diǎn)N'建立哈希映射<N,N'>）

第一次遍歷，建立簡(jiǎn)單節(jié)點(diǎn)，第二次遍歷，對(duì)于舊鏈表中的每一個(gè)節(jié)點(diǎn)的sibling指針地址，從map中找到新鏈表中對(duì)應(yīng)節(jié)點(diǎn)的地址，連接上就好了。

實(shí)現(xiàn)：（不錯(cuò)的實(shí)現(xiàn)，學(xué)習(xí)）

ComplexNode* Clone(ComplexNode*pHead){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(pHead == NULL) <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return NULL;<span class="hljs-built_in" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 134, 179); background: transparent;">map<ComplexNode*, ComplexNode*>pointMap;ComplexNode* newHead,*tail; <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// newHead指向復(fù)制的新鏈表的開(kāi)頭，tail始終指向結(jié)尾<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// 開(kāi)辟一個(gè)頭結(jié)點(diǎn)newHead = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new ComplexNode;newHead->value = pHead->value;newHead->pNext = NULL;newHead->pSibling = NULL;pointMap[pHead] = newHead; <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// 將頭結(jié)點(diǎn)放入map中tail = newHead;ComplexNode *p = pHead->pNext;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(p != NULL){ <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// 第一遍先將簡(jiǎn)單鏈表復(fù)制一下ComplexNode* newNode = <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new ComplexNode;newNode->value = p->value;newNode->pNext = NULL;newNode->pSibling = NULL;tail->pNext = newNode;tail = newNode;pointMap[p] = newNode;p = p->pNext;}<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">// 根據(jù)map中保存的數(shù)據(jù)，找到對(duì)應(yīng)的節(jié)點(diǎn)p = pHead;tail = newHead;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(p!=NULL){<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(p->pSibling!=NULL){tail->pSibling =pointMap.find(p->pSibling)->second;<span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//Key，找N對(duì)應(yīng)的N’}p = p->pNext;tail = tail->pNext;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return newHead;}

思路二：（精妙）一個(gè)技巧便可以巧妙的解答此題?？磮D便知。

首先是原始的鏈表

然后我們還是首先復(fù)制每一個(gè)結(jié)點(diǎn)N為N*，不同的是我們將N*讓在對(duì)應(yīng)的N后面，即為

然后我們要確定每一個(gè)N*的sibling分量，非常明顯，N的sibling分量的next就是N*的sibling分量。

最后，將整個(gè)鏈表拆分成原始鏈表和拷貝出的鏈表。

這樣，我們就解決了一個(gè)看似非?；靵y和復(fù)雜的問(wèn)題。

實(shí)現(xiàn)：

<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">struct Node{<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">int val;Node* next;Node*sibling; }; <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">void <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">Clone<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(Node* head){Node*current=head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(current){Node*temp=<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">new Node;temp->val=current->val;temp->next=current->next;temp->sibling=NULL;current->next=temp;current=temp->next;} } <span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">void <span class="hljs-title" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(25, 70, 157); background: transparent;">ConstructSibling<span class="hljs-params" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(0, 0, 255); background: transparent;">(Node*head){Node*origin=head;Node*clone;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(origin){clone=origin->next;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(origin->sibling)clone->sibling=origin->sibling->next;origin=clone->next;} }Node* Split(Node* head){Node*CloneHead,*clone,*origin;origin=head;<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">if(origin){CloneHead=origin->next;origin->next=CloneHead->next;origin=CloneHead->next;clone=CloneHead;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">while(origin){Node*temp=origin->next;origin->next=temp->next;origin=origin->next;clone->next=temp;clone=temp;}<span class="hljs-keyword" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: inherit; font-family: inherit; vertical-align: baseline; color: rgb(149, 65, 33); background: transparent;">return CloneHead; } <span class="hljs-comment" style="border: 0px; margin: 0px; padding: 0px; font-weight: inherit; font-style: italic; font-family: inherit; vertical-align: baseline; color: rgb(64, 128, 128); background: transparent;">//the whole thing Clone(head); ConstructSibling(head); Split(head); 轉(zhuǎn)載自：http://www.voidcn.com/blog/ywok526/article/p-2520659.html

總結(jié)

以上是生活随笔為你收集整理的链表面试笔试题目总结的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：读 Joseph J. Rotman 之
下一篇： python实现图片拼接长图_用Pyth