Python程序員面試分類真題2

Python程序員面試分類真題2(總分：100.00，做題時(shí)間：90分鐘)面試題(總題數(shù)：6，分?jǐn)?shù)：100.00)1.

把鏈表相鄰元素翻轉(zhuǎn)，例如給定鏈表為1-＞2-＞3-＞4-＞5-＞6-＞7，則翻轉(zhuǎn)后的鏈表變?yōu)?-＞1-＞4-＞3-＞6-＞5-＞7。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(方法一：交換值法

最容易想到的方法就是交換相鄰兩個(gè)結(jié)點(diǎn)的數(shù)據(jù)域，這種方法由于不需要重新調(diào)整鏈表的結(jié)構(gòu)，因此，比較容易實(shí)現(xiàn)，但是這種方法并不是考官所期望的解法。

方法二：就地逆序

主要思路：通過調(diào)整結(jié)點(diǎn)指針域的指向來直接調(diào)換相鄰的兩個(gè)結(jié)點(diǎn)。如果單鏈表恰好有偶數(shù)個(gè)結(jié)點(diǎn)，那么只需要將奇偶結(jié)點(diǎn)對調(diào)即可，如果鏈表有奇數(shù)個(gè)結(jié)點(diǎn)，那么只需要將除最后一個(gè)結(jié)點(diǎn)外的其它結(jié)點(diǎn)進(jìn)行奇偶對調(diào)即可。為了便于理解，下圖給出了其中第一對結(jié)點(diǎn)對調(diào)的方法。

在上圖中，當(dāng)前遍歷到結(jié)點(diǎn)cur，通過(1)～(6)6個(gè)步驟用虛線的指針來代替實(shí)線的指針實(shí)現(xiàn)相鄰結(jié)點(diǎn)的逆序。其中，(1)～(4)實(shí)現(xiàn)了前兩個(gè)結(jié)點(diǎn)的逆序操作，(5)和(6)兩個(gè)步驟向后移動指針，接著可以采用同樣的方式實(shí)現(xiàn)后面兩個(gè)相鄰結(jié)點(diǎn)的逆序操作。實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#把鏈表相鄰元素翻轉(zhuǎn)

defreverse(head):

#判斷鏈表是否為空

ifhead==Noneorhead.next==None:

return

cur=head.next#當(dāng)前遍歷結(jié)點(diǎn)

pre=head#當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)

next=None#當(dāng)前結(jié)點(diǎn)后繼結(jié)點(diǎn)的后繼結(jié)點(diǎn)

whilecur!=Noneandcur.next!=None:

next=cur.next.next#見圖第(1)步

pre.next=cur.next#見圖第(2)步

cur.next.next=cur#見圖第(3)步

cur.next=next#見圖第(4)步

pre=cur#見圖第(5)步

cur=next#見圖第(6)步

if__name__=="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"順序輸出:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

reverse(head)

print"\n逆序輸出:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

cur=head.next

whilecur!=None:

cur=cur.next

程序的運(yùn)行結(jié)果為：

順序輸出：1234567

逆序輸出：2143657

上例中，由于鏈表有奇數(shù)個(gè)結(jié)點(diǎn)，因此，鏈表前三對結(jié)點(diǎn)相互交換，而最后一個(gè)結(jié)點(diǎn)保持在原來的位置。

算法性能分析：

這種方法只需要對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(n)。另外由于只需要幾個(gè)指針變量來保存結(jié)點(diǎn)的地址信息，因此，空間復(fù)雜度為O(1)。)解析：[考點(diǎn)]如何把鏈表相鄰元素翻轉(zhuǎn)2.

K鏈表翻轉(zhuǎn)是指把每K個(gè)相鄰的結(jié)點(diǎn)看成一組進(jìn)行翻轉(zhuǎn)，如果剩余結(jié)點(diǎn)不足K個(gè)，則保持不變。假設(shè)給定鏈表1-＞2-＞3-＞4-＞5-＞6-＞7和一個(gè)數(shù)K，如果K的值為2，那么翻轉(zhuǎn)后的鏈表為2-＞1＞4-＞3-＞6-＞5-＞7。如果K的值為3，那么翻轉(zhuǎn)后的鏈表為：3-＞2-＞1-＞6-＞5-＞4-＞7。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(主要思路為：首先把前K個(gè)結(jié)點(diǎn)看成一個(gè)子鏈表，采用前面介紹的方法進(jìn)行翻轉(zhuǎn)，把翻轉(zhuǎn)后的子鏈表鏈接到頭結(jié)點(diǎn)后面，然后把接下來的K個(gè)結(jié)點(diǎn)看成另外一個(gè)單獨(dú)的鏈表進(jìn)行翻轉(zhuǎn)，把翻轉(zhuǎn)后的子鏈表鏈接到上一個(gè)已經(jīng)完成翻轉(zhuǎn)子鏈表的后面。具體實(shí)現(xiàn)方法如下圖所示。

在上圖中，以K=3為例介紹具體實(shí)現(xiàn)的方法：

(1)首先設(shè)置pre指向頭結(jié)點(diǎn)，然后讓begin指向鏈表第一個(gè)結(jié)點(diǎn)，找到從begin開始第K=3個(gè)結(jié)點(diǎn)end。

(2)為了采用本章第一節(jié)中鏈表翻轉(zhuǎn)的算法，需要使end.next=None在此之前需要記錄下end指向的結(jié)點(diǎn)，用pNext來記錄。

(3)使end.next=None，從而使得從begin到end為一個(gè)單獨(dú)的子鏈表。

(4)對以begin為第一個(gè)結(jié)點(diǎn)，end為尾結(jié)點(diǎn)所對應(yīng)的K=3個(gè)結(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)。

(5)由于翻轉(zhuǎn)后子鏈表的第一個(gè)結(jié)點(diǎn)從begin變?yōu)閑nd，因此，執(zhí)行pre.next=end，把翻轉(zhuǎn)后的子鏈表鏈接起來。

(6)把鏈表中剩余的還未完成翻轉(zhuǎn)的子鏈表鏈接到已完成翻轉(zhuǎn)的子鏈表后面(主要是針對剩余的結(jié)點(diǎn)的個(gè)數(shù)小于K的情況)。

(7)讓pre指針指向已完成翻轉(zhuǎn)的鏈表的最后一個(gè)結(jié)點(diǎn)。

(8)讓begin指針指向下一個(gè)需要被翻轉(zhuǎn)的子鏈表的第一個(gè)結(jié)點(diǎn)(通過begin=pNext來實(shí)現(xiàn))。

接下來可以反復(fù)使用(1)～(8)8個(gè)步驟對鏈表進(jìn)行翻轉(zhuǎn)。實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#對不帶頭結(jié)點(diǎn)的單鏈表翻轉(zhuǎn)

defReverse(head):

ifhead==Noneorhead.next==None:

returnhead

pre=head#前驅(qū)結(jié)點(diǎn)

cur=head.next#當(dāng)前結(jié)點(diǎn)

next=cur.next#后繼結(jié)點(diǎn)

pre.next=None

#使當(dāng)前遍歷到的結(jié)點(diǎn)cur指向其前驅(qū)結(jié)點(diǎn)

whilecur!=None:

next=cur.next

cur.next=pre

pre=cur

cur=cur.next

cur=next

returnpre

#對鏈表K翻轉(zhuǎn)

defReverseK(head,k):

ifhead==Noneorhead.next==Noneork＜2:

return

i=1

pre=head

begin=head.next

end=None

pNext=None

whilebegin!=None:

end=begin

#對應(yīng)圖中第(1)步,找到從begin開始第K個(gè)結(jié)點(diǎn)

whilei＜k:

ifend.next!=None:

end=end.next

else:#剩余結(jié)點(diǎn)的個(gè)數(shù)小于K

return

i+=1

pNext=end.next#(2)

end.next=None#(3)

pre.next=Reverse(begin)#(4)(5)

begin.next=pNext#(6)

pre=begin#(7)

begin=pNext#(8)

i=1

if__name__=="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"順序輸出:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

ReverseK(head,3)

print"\n逆序輸出:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

cur=head.next

whilecur!=None:

tmp=cur

cur=cur.next

程序的運(yùn)行結(jié)果為：

順序輸出：1234567

逆序輸出：3216547

運(yùn)行結(jié)果分析：

由于K=3，因此，鏈表可以分成三組(123)、(456)、(7)。對(123)翻轉(zhuǎn)后變?yōu)?321)，對(456)翻轉(zhuǎn)后變?yōu)?654)，由于(7)這個(gè)子鏈表只有1個(gè)結(jié)點(diǎn)(小于3個(gè))，因此，不進(jìn)行翻轉(zhuǎn)，所以，翻轉(zhuǎn)后的鏈表就變?yōu)椋?-＞2-＞1-＞6-＞5-＞4-＞7。

算法性能分析：

這種方法只需要對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(n)。另外由于只需要幾個(gè)指針變量來保存結(jié)點(diǎn)的地址信息，因此，空間復(fù)雜度為O(1)。)解析：[考點(diǎn)]如何把鏈表以K個(gè)結(jié)點(diǎn)為一組進(jìn)行翻轉(zhuǎn)3.

已知兩個(gè)鏈表head1和head2各自有序(例如升序排列)，請把它們合并成一個(gè)鏈表，要求合并后的鏈表依然有序。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(分別用指針head1，head2來遍歷兩個(gè)鏈表，如果當(dāng)前head1指向的數(shù)據(jù)小于head2指向的數(shù)據(jù)，則將head1指向的結(jié)點(diǎn)歸入合并后的鏈表中，否則，將head2指向的結(jié)點(diǎn)歸入合并后的鏈表中。如果有一個(gè)鏈表遍歷結(jié)束，則把未結(jié)束的鏈表連接到合并后的鏈表尾部。

下圖以一個(gè)簡單的示例為例介紹合并的具體方法：

由于鏈表按升序排列，首先通過比較鏈表第一個(gè)結(jié)點(diǎn)中元素的大小來確定最終合并后鏈表的頭結(jié)點(diǎn)；接下來每次都找兩個(gè)鏈表中剩余結(jié)點(diǎn)的最小值鏈接到被合并的鏈表后面，如上圖中的虛線所示。具體實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#方法功能:構(gòu)造鏈表

defConstructList(start):

i=start

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜7:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=2

returnhead

defPrintList(head):

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

"""

方法功能:合并兩個(gè)升序排列的單鏈表

輸入?yún)?shù):head1與head2代表兩個(gè)單鏈表

返回值:合并后鏈表的頭結(jié)點(diǎn)

"""

defMerge(head1,head2):

ifhead1==Noneorhead1.next==None:

returnhead2

ifhead2==Noneorhead2.next==None:

returnhead1

cur1=head1.next#用來遍歷head1

cur2=head2.next#用來遍歷head2

head=None#合并后鏈表的頭結(jié)點(diǎn)

cur=None#合并后的鏈表在尾結(jié)點(diǎn)

#合并后鏈表的頭結(jié)點(diǎn)為第一個(gè)結(jié)點(diǎn)元素最小的那個(gè)鏈表的頭結(jié)點(diǎn)

ifcur1.data＞cur2.data:

head=head2

cur=cur2

cur2=cur2.next

else:

head=head1

cur=cur1

cur1=cur1.next

#每次找鏈表剩余結(jié)點(diǎn)的最小值對應(yīng)的結(jié)點(diǎn)連接到合并后鏈表的尾部

whilecur1!=Noneandcur2!=None:

ifcur1.data＜cur2.data:

cur.next=cur1

cur=cur1

cur1=cur1.next

else:

cur.next=cur2

cur=cur2

cur2=cur2.next

#當(dāng)遍歷完一個(gè)鏈表后把另外一個(gè)鏈表剩余的結(jié)點(diǎn)鏈接到合并后的鏈表后面

ifcur1!=None:

cur.next=cur1

ifcur2!=None:

cur.next=cur2

returnhead

if__name__=="__main__":

head1=ConstructList(1)

head2=ConstructList(2)

print"head1:",

PrintList(head1)

print"\nhead2:",

PrintList(head2)

print"\n合并后的鏈表:",

head=Merge(head1,head2)

PrintList(head)

程序的運(yùn)行結(jié)果為：

head1:1

3

5

head2:2

4

6

合并后的鏈表：123456

算法性能分析：

以上這種方法只需要對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O(n)。另外由于只需要幾個(gè)指針變量來保存結(jié)點(diǎn)的地址信息，因此，空間復(fù)雜度為O(1)。)解析：[考點(diǎn)]如何合并兩個(gè)有序鏈表4.

假設(shè)給定鏈表1-＞2-＞3-＞4-＞5-＞6-＞7中指向第5個(gè)元素的指針，要求把結(jié)點(diǎn)5刪掉，刪除后鏈表變?yōu)?-＞2-＞3-＞4-＞6-＞7。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(一般而言，要刪除單鏈表中的一個(gè)結(jié)點(diǎn)p，首先需要找到結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)pre，然后通過pre.next=p.next來實(shí)現(xiàn)對結(jié)點(diǎn)p的刪除。對于本題而言，由于無法獲取到結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)，因此，不能采用這種傳統(tǒng)的方法。

那么如何解決這個(gè)問題呢?可以分如下兩種情況來分析：

(1)如果這個(gè)結(jié)點(diǎn)是鏈表的最后一個(gè)結(jié)點(diǎn)，那么無法刪除這個(gè)結(jié)點(diǎn)。

(2)如果這個(gè)結(jié)點(diǎn)不是鏈表的最后一個(gè)結(jié)點(diǎn)，可以通過把其后繼結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到當(dāng)前結(jié)點(diǎn)中，然后刪除后繼結(jié)點(diǎn)的方法來實(shí)現(xiàn)。實(shí)現(xiàn)方法如下圖所示：

在上圖中，首先把結(jié)點(diǎn)p的后繼結(jié)點(diǎn)的數(shù)據(jù)復(fù)制到結(jié)點(diǎn)p的數(shù)據(jù)域中；接著把結(jié)點(diǎn)p的后繼結(jié)點(diǎn)刪除。實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

defprintList(head):

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

"""

方法功能:給定單鏈表中某個(gè)結(jié)點(diǎn),刪除該結(jié)點(diǎn)

輸入?yún)?shù):鏈表中某結(jié)點(diǎn)

返回值:true:刪除成功;false:刪除失敗

"""

defRemoveNode(p):

#如果結(jié)點(diǎn)為空,或結(jié)點(diǎn)p無后繼結(jié)點(diǎn)則無法刪除

ifp==Noneorp.next==None:

returnFalse

p.data=p.next.data

tmp=p.next

p.next=tmp.next

returnTrue

if__name__=="__main__":

i=1

head=LNode()#鏈表頭結(jié)點(diǎn)

head.next=None

tmp=None

cur=head

p=None

#構(gòu)造鏈表

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

ifi=5:

p=tmp

i+=1

print"刪除結(jié)點(diǎn)"+str(p.data)+"前鏈表:",

printList(head)

result=RemoveNode(p)

ifresult:

print"\n刪除該結(jié)點(diǎn)后鏈表:",

printList(head)

程序的運(yùn)行結(jié)果為：

刪除結(jié)點(diǎn)5前鏈表：1234567

刪除該結(jié)點(diǎn)后鏈表：123467

算法性能分析：

由于這種方法不需要遍歷鏈表，只需要完成一個(gè)數(shù)據(jù)復(fù)制與結(jié)點(diǎn)刪除的操作，因此，時(shí)間復(fù)雜度為O(1)。由于這種方法只用了常數(shù)個(gè)額外指針變量，因此，空間復(fù)雜度也為O(1)。)解析：[考點(diǎn)]如何在只給定單鏈表中某個(gè)結(jié)點(diǎn)的指針的情況下刪除該結(jié)點(diǎn)5.

單鏈表相交指的是兩個(gè)鏈表存在完全重合的部分，如下圖所示：

在上圖中，這兩個(gè)鏈表相交于結(jié)點(diǎn)5，要求判斷兩個(gè)鏈表是否相交，如果相交，找出相交處的結(jié)點(diǎn)。

（分?jǐn)?shù)：16.50）__________________________________________________________________________________________

正確答案：(方法一：Hash法

如上圖所示，如果兩個(gè)鏈表相交，那么它們一定會有公共的結(jié)點(diǎn)，由于結(jié)點(diǎn)的地址或引用可以作為結(jié)點(diǎn)的唯一標(biāo)識，因此，可以通過判斷兩個(gè)鏈表中的結(jié)點(diǎn)是否有相同的地址或引用來判斷鏈表是否相交。具體可以采用如下方法實(shí)現(xiàn)：首先遍歷鏈表head1，把遍歷到的所有結(jié)點(diǎn)的地址存放到HashSet中；接著遍歷鏈表head2，每遍歷到一個(gè)結(jié)點(diǎn)，就判斷這個(gè)結(jié)點(diǎn)的地址在HashSet中是否存在，如果存在，那么說明兩個(gè)鏈表相交并且當(dāng)前遍歷到的結(jié)點(diǎn)就是它們的相交點(diǎn)，否則直接將鏈表head2遍歷結(jié)束，說明這兩個(gè)單鏈表不相交。

算法性能分析：

由于這種方法需要分別遍歷兩個(gè)鏈表，因此，算法的時(shí)間復(fù)雜度為O(n1+n2)，其中，n1與n2分別為兩個(gè)鏈表的長度。此外，由于需要申請額外的存儲空間來存儲鏈表head1中結(jié)點(diǎn)的地址，因此，算法的空間復(fù)雜度為O(n1)。

方法二：首尾相接法

主要思路：將這兩個(gè)鏈表首尾相連(例如把鏈表head1尾結(jié)點(diǎn)鏈接到head2的頭指針)，然后檢測這個(gè)鏈表是否存在環(huán)，如果存在，則兩個(gè)鏈表相交，而環(huán)入口結(jié)點(diǎn)即為相交的結(jié)點(diǎn)，如下圖所示。

方法三：尾結(jié)點(diǎn)法

主要思路：如果兩個(gè)鏈表相交，那么兩個(gè)鏈表從相交點(diǎn)到鏈表結(jié)束都是相同的結(jié)點(diǎn)，必然是Y字形(如上圖所示)，所以，判斷兩個(gè)鏈表的最后一個(gè)結(jié)點(diǎn)是不是相同即可。即先遍歷一個(gè)鏈表，直到尾部，再遍歷另外一個(gè)鏈表，如果也可以走到同樣的結(jié)尾點(diǎn)，則兩個(gè)鏈表相交，這時(shí)記下兩個(gè)鏈表的長度n1、n2，再遍歷一次，長鏈表結(jié)點(diǎn)先出發(fā)前進(jìn)|n1-n2|步，之后兩個(gè)鏈表同時(shí)前進(jìn)，每次一步，相遇的第一點(diǎn)即為兩個(gè)鏈表相交的第一個(gè)點(diǎn)。實(shí)現(xiàn)代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

方法功能:判斷兩個(gè)鏈表是否相交,如果相交找出交點(diǎn)

輸入?yún)?shù):head1與head2分別為兩個(gè)鏈表的頭結(jié)點(diǎn)

返回值:如果不相交返回None,如果相交返回相交結(jié)點(diǎn)

"""

defIslntersect(head1,head2):

ifhead1==Noneorhead1.next==Noneorhead2==Noneor\

head2.next==Noneorhead1==head2:

returnNone

temp1=head1.next

temp2=head2.next

n1,n2=0,0

#遍歷head1,找到尾結(jié)點(diǎn),同時(shí)記錄head1的長度

whiletemp1.next!=None:

temp1=temp1.next

n1+=1

#遍歷head2,找到尾結(jié)點(diǎn),同時(shí)記錄head2的長度

whiletemp2.next!=None:

temp2=temp2.next

n2+=1

#head1與head2是有相同的尾結(jié)點(diǎn)

iftemp1==temp2:

#長鏈表先走|n1-n2|步

ifn1＞n2:

whilen1-n2＞0:

head1=head1.next

n1-=1

ifn2＞n1:

whilen2-n1＞0:

head2=head2.next

n2==1

#兩個(gè)鏈表同時(shí)前進(jìn),找出相同的結(jié)點(diǎn)

whilehead1!=head2:

head1=head1.next

head2=head2.next

returnhead1

#head1與head2是沒有相同的尾結(jié)點(diǎn)

else:

returnNone

if__name__="__main__":

i=1

#鏈表頭結(jié)點(diǎn)

head1=LNode()

head1.next=None

#鏈表頭結(jié)點(diǎn)

head2=LNode()

head2.next=None

tmp=None

cur=head1

p=None

#構(gòu)造第1個(gè)鏈表

whilei＜8:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

if(i==5):

p=tmp

i+=1

cur=head2

#構(gòu)造第2個(gè)鏈表

i=1

whilei＜5:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

#使它們相交于結(jié)點(diǎn)5

cur.next=p

interNode=IsIntersect(head1,head2)

ifinterNode==None:

print"這兩個(gè)鏈表不相交:"

else:

print"這兩個(gè)鏈表相交點(diǎn)為:"+str(interNode.data)

程序的運(yùn)行結(jié)果為：

這兩個(gè)鏈表相交點(diǎn)為：5

運(yùn)行結(jié)果分析：

在上述代碼中，由于構(gòu)造的兩個(gè)單鏈表相交于結(jié)點(diǎn)5，因此，輸出結(jié)果中它們的相交結(jié)點(diǎn)為5。

算法性能分析：

假設(shè)這兩個(gè)鏈表長度分別為n1，n2，重疊的結(jié)點(diǎn)的個(gè)數(shù)為L(0＜L＜min(n1,n2))，則總共對鏈表進(jìn)行遍歷的次數(shù)為n1+n2+L+n1-L+n2-L=2(n1+n2)-L，因此，算法的時(shí)間復(fù)雜度為O(n1+n2)；由于這種方法只使用了常數(shù)個(gè)額外指針變量，因此，空間復(fù)雜度為O(1)。)解析：[考點(diǎn)]如何判斷兩個(gè)單鏈表(無環(huán))是否交叉6.

給定一個(gè)有序鏈表，其中每個(gè)結(jié)點(diǎn)也表示一個(gè)有序鏈表，結(jié)點(diǎn)包含兩個(gè)類型的指針：

(1)指向主鏈表中下一個(gè)結(jié)點(diǎn)的指針(在下面的代碼中稱為“正確”指針)

(2)指向此結(jié)點(diǎn)頭的鏈表(在下面的代碼中稱之為“down”指針)。

所有鏈表都被排序。請參見以下示例：

實(shí)現(xiàn)一個(gè)函數(shù)flatten()，該函數(shù)用來將鏈表扁平化成單個(gè)鏈表，扁平化的鏈表也應(yīng)該被排序。例如，對于上述輸入鏈表，輸出鏈表應(yīng)為3-＞6-＞8-＞11-＞15-＞21-＞22-＞30-＞31-＞39-＞40-＞45-＞50。

（分?jǐn)?shù)：17.50）__________________________________________________________________________________________

正確答案：(本題的主要思路為使用歸并排序中的合并操作，使用歸并的方法把這些鏈表來逐個(gè)歸并。具體而言，可以使用遞歸的方法，遞歸地合并已經(jīng)扁平化的鏈表與當(dāng)前的鏈表。在實(shí)現(xiàn)的過程可以使用down指針來存儲扁平化處理后的鏈表。實(shí)現(xiàn)代碼如下：

classNode:

def__init__(self,data):

self.data=data

#self.next=None

self.right=None

self.down=None

#self.head=None

classMergeList:

def__init__(self):

self.head=None

#用來合并兩個(gè)有序的鏈表*

defmerge(self,a,b):

#如果有其中一個(gè)鏈表為空,直接返回另外一個(gè)鏈表

ifa==None:

returnb

ifb==None:

returna

#把兩個(gè)鏈表頭中較小的結(jié)點(diǎn)賦值給result

ifa.data＜b.data:

result=a

result.down=self.merge(a.down,b)

else:

result=b

result.down=self.merge(a,b.down)

returnresult

#把鏈表扁平化處理

defflatten(self,root):

ifroo