Python程序員面試分類真題11.

給定一個帶頭結點的單鏈表，請將其逆序。即如果單鏈表原來為head-＞1-＞2-＞3-＞4-＞5-＞6-＞7，那么逆序后變為head-＞7-＞6-＞5-＞4-＞3-＞2-（江南博哥）＞1。正確答案：由于單鏈表與數組不同，單鏈表中每個結點的地址都存儲在其前驅結點的指針域中，因此，對單鏈表中任何一個結點的訪問只能從鏈表的頭指針開始進行遍歷。在對鏈表的操作過程中，需要特別注意在修改結點指針域的時候，記錄下后繼結點的地址，否則會丟失后繼結點。

方法一：就地逆序

主要思路為：在遍歷鏈表的時候，修改當前結點的指針域的指向，讓其指向它的前驅結點。為此需要用一個指針變量來保存前驅結點的地址。此外，為了在調整當前結點指針域的指向后還能找到后繼結點，還需要另外一個指針變量來保存后繼結點的地址，在所有的結點都被保存好以后就可以直接完成指針的逆序了。除此之外，還需要特別注意對鏈表首尾結點的特殊處理。具體實現方式如下圖所示。

在上圖中，假設當前已經遍歷到cur結點，由于它所有的前驅結點都已經完成了逆序操作，因此，只需要使cur.next=pre即可完成逆序操作，在此之前，為了能夠記錄當前結點的后繼結點的地址，需要用一個額外的指針next來保存后繼結點的信息，通過上圖(1)～(4)四步把實線的指針調整為虛線的指針就可以完成當前結點的逆序。當前結點完成逆序后，通過向后移動指針來對后續的結點用同樣的方法進行逆序操作。算法實現如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#方法功能:對單鏈表進行逆序輸入參數:head:鏈表頭結點

defReverse(head):

#判斷鏈表是否為空

ifhead==Noneorhead.next==None:

return

pre=None#前驅結點

cur=None#當前結點

next=None#后繼結點

#把鏈表首結點變為尾結點

cur=head.next

next=cur.next

cur.next=None

pre=cur

cur=next

#使當前遍歷到的結點cur指向其前驅結點

whilecur.next!=Node:

next=cur.next

cur.next=pre

pre=cur

cur=cur.next

cur=next

#鏈表最后一個結點指向倒數第二個結點

cur.next=pre

#鏈表的頭結點指向原來鏈表的尾結點

head.next=cur

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

print"\n逆序后:",

Reverse(head)

cur=head.next

whilecur!=None:

printcur.data,

Cur=cur.next

程序的運行結果為：

逆序前：1234567

逆序后：7654321

算法性能分析：

以上這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(N)，其中，N為鏈表的長度。但是需要常數個額外的變量來保存當前結點的前驅結點與后繼結點，因此，空間復雜度為O(1)。

方法二：遞歸法

假定原鏈表為1-＞2-＞3-＞4-＞5-＞6-＞7，遞歸法的主要思路為：先逆序除第一個結點以外的子鏈表(將1-＞2-＞3-＞4-＞5-＞6-＞7變為1-＞7-＞6-＞5-＞4-＞3-＞2)，接著把結點1添加到逆序的子鏈表的后面(1-＞7-＞6-＞5-＞4-＞3-＞2變為7-＞6-＞5-＞4-＞3-＞2-＞1)。同理，在逆序鏈表2-＞3-＞4-＞5-＞6-＞7時，也是先逆序子鏈表3-＞4-＞5-＞6-＞7(逆序為2-＞7-＞6-＞5-＞4-＞3)，接著實現鏈表的整體逆序(2-＞7-＞6-＞5-＞4-＞3轉換為7-＞6-＞5-＞4-＞3-＞2)。實現代碼如下：

"""

方法功能:對不帶頭結點的單鏈表進行逆序

輸入參數:firstRef:鏈表頭結點

"""

defRecursiveReverse(head):

#如果鏈表為空或者鏈表中只有一個元素

ifheadisNoneorhead.nextisNone:

returnhead

else:

#反轉后面的結點

newhead=RecursiveReverse(head.next)

#把當前遍歷的結點加到后面結點逆序后鏈表的尾部

head.next.next=head

head.next=None

returnnewhead

"""

方法功能:對帶頭結點的單鏈表進行逆序

輸入參數:head:鏈表頭結點

"""

defReverse(head):

ifheadisNone:

return

#獲取鏈表第一個結點

firstNode=head.next

#對鏈表進行逆序

newhead=RecursiveReverse(firstNode)

#頭結點指向逆序后鏈表的第一個結點

head.next=newhead

returnnewhead

算法性能分析：

由于遞歸法也只需要對鏈表進行一次遍歷，因此，算法的時間復雜度也為O(N)，其中，N為鏈表的長度。遞歸法的主要優點是：思路比較直觀，容易理解，而且也不需要保存前驅結點的地址。缺點是：算法實現的難度較大，此外，由于遞歸法需要不斷地調用自己，需要額外的壓棧與彈棧操作，因此，與方法一相比性能會有所下降。

方法三：插入法

插入法的主要思路為：從鏈表的第二個結點開始，把遍歷到的結點插入到頭結點的后面，直到遍歷結束。假定原鏈表為head-＞1＞2-＞3-＞4-＞5-＞6-＞7，在遍歷到2的時候，將其插入到頭結點后，鏈表變為head-＞2-＞1＞3-＞4-＞5-＞6-＞7，同理將后序遍歷到的所有結點都插入到頭結點head后，就可以實現鏈表的逆序。實現代碼如下：

defReverse(head):

#判斷鏈表是否為空

ifheadisNoneorhead.nextisNone:

return

cur=None#當前結點

next=None#后繼結點

cur=head.next.next

#設置鏈表第一個結點為尾結點

head.next.next=None

#把遍歷到結點插入到頭結點的后面

whilecurisnotNone:

next=cur.next

cur.next=head.next

head.next=cur

cur=next

算法性能分析：

以上這種方法也只需要對單鏈表進行一次遍歷，因此，時間復雜度為O(N)，其中，N為鏈表的長度。與方法一相比，這種方法不需要保存前驅結點的地址，與方法二相比，這種方法不需要遞歸地調用，效率更高。[考點]如何實現鏈表的逆序

2.

給定一個沒有排序的鏈表，去掉其重復項，并保留原順序，例如鏈表1-＞3-＞1＞5-＞5-＞7,去掉重復項后變為1-＞3-＞5-＞7。正確答案：方法一：順序刪除

主要思路為：通過雙重循環直接在鏈表上進行刪除操作。外層循環用一個指針從第一個結點開始遍歷整個鏈表，然后內層循環用另外一個指針遍歷其余結點，將與外層循環遍歷到的指針所指結點的數據域相同的結點刪除。如下圖所示：

假設外層循環從outerCur開始遍歷，當內層循環指針innerCur遍歷到上圖實線所示的位置(outerCur.data==innerCur.data)時，需要把innerCur指向的結點刪除。具體步驟如下：

(1)用tmp記錄待刪除的結點的地址。

(2)為了能夠在刪除tmp結點后繼續遍歷鏈表中其余的結點，使innerCur指向它的后繼結點：innerCUFinnerCur.next。

(3)從鏈表中刪除tmp結點。

實現代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

**方法功能:對帶頭結點的無序單鏈表刪除重復的結點

**輸入參數:head:鏈表頭結點

"""

defremoveDup(head):

ifhead==Noneorhead.next==None:

return

outerCur=head.next#用于外層循環,指向鏈表第一個結點

innerCur=None#用于內層循環用來遍歷outerCur后面的結點

innerPre=None#innerCur的前驅結點

whileouterCur!=None:

innerCur=outerCur.next

innerPre=outerCur

whileinnerCur!=None:

#找到重復的結點并刪除

ifouterCur.data==innerCur.data:

innerPre.next=innerCur.next

innerCur=innerCur.next

else:

innerPre=innerCur

innerCur=innerCur.next

outerCur=outerCur.next

if__name__="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

whilei＜7:

tmp=LNode()

ifi%2=0:

tmp.data=i+1

elifi%3=0:

tmp.data=i-2

else:

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

print"刪除重復結點前:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

removeDup(head)

print"\n刪除重復結點后:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

程序的運行結果為：

刪除重復結點前：131557

刪除重復結點后：1357

算法性能分析：

由于這種方法采用雙重循環對鏈表進行遍歷，因此，時間復雜度為O(N2)，其中，N為鏈表的長度，在遍歷鏈表的過程中，使用了常量個額外的指針變量來保存當前遍歷的結點、前驅結點和被刪除的結點，因此，空間復雜度為O(1)。

方法二：遞歸法

主要思路為：對于結點cur，首先遞歸地刪除以cur.next為首的子鏈表中重復的結點，接著從以cur.next為首的子鏈表中找出與cur有著相同數據域的結點并刪除，實現代碼如下：

defremoveDupRecursion(head):

ifhead.nextisNone:

returnhead

pointer=None

cur=head

#對以head.next為首的予鏈表刪除重復的結點

head.next=removeDupRecursion(head.next)

pointer=head.next

#找出以head.next為首的子鏈表中與head結點相同的結點并刪除

whilepointerisnotNone:

ifhead.data=pointer.data:

cur.next=pointer.next

pointer=cur.next

else:

pointer=pointer.next

cur=cur.next

returnhead

"""

方法功能:對帶頭結點的單鏈刪除重復結點輸入參數:head:鏈表頭結點

"""

defremoveDup(head):

if(headisNone):

return

head.next=removeDupRecursion(head.next)

算法性能分析：

這種方法與方法一類似，從本質上而言，由于這種方法需要對鏈表進行雙重遍歷，因此，時間復雜度為O(N2)，其中，N為鏈表的長度。由于遞歸法會增加許多額外的函數調用，因此，從理論上講，該方法效率比方法一低。

方法三：空間換時間

通常情況下，為了降低時間復雜度，往往在條件允許的情況下，通過使用輔助空間來實現。具體而言，主要思路為：

(1)建立一個HashSet，HashSet中的內容為已經遍歷過的結點內容，并將其初始化為空。

(2)從頭開始遍歷鏈表中的所有結點，存在以下兩種可能性：

1)如果結點內容已經在HashSet中，那么刪除此結點，繼續向后遍歷。

2)如果結點內容不在HashSet中，那么保留此結點，將此結點內容添加到HashSet中，繼續向后遍歷。[考點]如何從無序鏈表中移除重復項

3.

給定兩個單鏈表，鏈表的每個結點代表一位數，計算兩個數的和。例如：輸入鏈表(3-＞1-＞5)和鏈表(5-＞9-＞2)，輸出：8-＞0-＞8，即513+295=808，注意個位數在鏈表頭。正確答案：方法一：整數相加法

主要思路：分別遍歷兩個鏈表，求出兩個鏈表所代表的整數的值，然后把這兩個整數進行相加，最后把它們的和用鏈表的形式表示出來。這種方法的優點是計算簡單，但是有個非常大的缺點：當鏈表所代表的數很大的時候(超出了long的表示范圍)，就無法使用這種方法了。

方法二：鏈表相加法

主要思路：對鏈表中的結點直接進行相加操作，把相加的和存儲到新的鏈表中對應的結點中，同時還要記錄結點相加后的進位。如下圖所示：

使用這種方法需要注意如下幾個問題：(1)每組結點進行相加后需要記錄其是否有進位；(2)如果兩個鏈表h1與h2的長度不同(長度分別為L1和L2，且L1＜L2)，當對鏈表的第L1位計算完成后，接下來只需要考慮鏈表L2剩余的結點的值(需要考慮進位)；(3)對鏈表所有結點都完成計算后，還需要考慮此時是否還有進位，如果有進位，則需要增加新的結點，此結點的數據域為1。實現代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

方法功能:對兩個帶頭結點的單鏈表所代表的數相加

輸入參數:h1:第一個鏈表頭結點;h2:第二個鏈表頭結點

返回值:相加后鏈表的頭結點

"""

defadd(h1,h2):

ifh1isNoneorh1.nextisNone:

returnh2

ifh2isNoneorh2.nextisNone:

returnh1

c=0#用來記錄進位

sums=0#用來記錄兩個結點相加的值

p1=h1.next#用來遍歷h1

p2=h2.next#用來遍歷h2

tmp=None#用來指向新創建的存儲相加和的結點

resultHead=LNode()#相加后鏈表頭結點

resultHead.next=None

p=resultHead#用來指向鏈表resultHead最后一個結點

whilep1isnotNoneandp2isnotNone:

tmp=LNode()

tmp.next=None

sums=p1.data+p2.data+c

tmp.data=sums%10#兩結點相加和

c=sums/10#進位

p.next=tmp

p=tmp

p1=p1.next

p2=p2.next

#鏈表h2比h1長,接下來只需要考慮h2剩余結點的值

ifp1isNone:

whilep2isnotNone:

tmp=LNode()

tmp.next=None

sums=p2.data+c

tmp.data=sums%10

c=sums/10

p.next=tmp

p=tmp

p2=p2.next

#鏈表h1比h2長,接下來只需要考慮h1剩余結點的值

ifp2isNone:

whilep1isnotNone:

tmp=LNode()

tmp.next=None

sums=p1.data+c

tmp.data=sums%10

c=sums/10

p.next=tmp

p=tmp

p1=p1.next

#如果計算完成后還有進位,則增加新的結點

ifc=1:

tmp=LNode()

tmp.next=None

tmp.data=1

p.next=tmp

returnresultHead

if__name__="__main__":

i=1

head1=LNode()

head1.next=None

head2=LNode()

head2.next=None

tmp=None

cur=head1

addResult=None

#構造第一個鏈表

whilei＜7:

tmp=LNode()

tmp.data=i+2

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

cur=head2

#構造第二個鏈表

i=9

whilei＞4:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i-=1

print"\nHead1:",

cur=head1.next

whilecurisnotNone:

printcur.data,

cur=cur.next

print"\nHead2:",

cur=head2.next

whilecurisnotNone:

printcur.data,

cur=cur.next

addResult=add(head1,head2)

print"\n相加后:",

cur=addResult.next

whilecurisnotNone:

printcur.data,

cur=cur.next

程序的運行結果為：

Head1：345678

Head2：98765

相加后：233339

運行結果分析：

前五位可以按照整數相加的方法依次從左到右進行計算，第五位7+5+1(進位)的值為3，進位為1。此時head2已經遍歷結束，由于head1還有結點沒有被遍歷，所以，依次接著遍歷head1剩余的結點：8+1(進位)=9，沒有進位。因此，運行代碼可以得到上述結果。

算法性能分析：

由于這種方法需要對兩個鏈表都進行遍歷，因此，時間復雜度為O(N)，其中，N為較長的鏈表的長度，由于計算結果保存在一個新的鏈表中，因此，空間復雜度也為O(N)。[考點]如何計算兩個單鏈表所代表的數之和

4.

給定鏈表L0-＞L1-＞L2…-Ln-1＞Ln，把鏈表重新排序為L0-＞Ln-＞L1-＞Ln-1＞L2-＞Ln-2…。要求：(1)在原來鏈表的基礎上進行排序，即不能申請新的結點；(2)只能修改結點的next域，不能修改數據域。正確答案：主要思路為：(1)首先找到鏈表的中間結點；(2)對鏈表的后半部分子鏈表進行逆序；

(3)把鏈表的前半部分子鏈表與逆序后的后半部分子鏈表進行合并，合并的思路為：分別從兩個鏈表各取一個結點進行合并。實現方法如下圖所示：

實現代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

方法功能:找出鏈表Head的中間結點,把鏈表從中間斷成兩個子鏈表輸入參數:head:鏈表頭結點

返回值:鏈表中間結點

"""

defFindMiddleNode(head):

ifheadisNoneorhead.nextisNone:

returnhead

fast=head#遍歷鏈表的時候每次向前走兩步

slow=head#遍歷鏈表的時候每次向前走一步

slowPre=head

#當fast到鏈表尾時,slow恰好指向鏈表的中間結點

whilefastisnotNoneandfast.nextiSnotNone:

slowPre=slow

slow=slow.next

fast=fast.next.next

#把鏈表斷開成兩個獨立的子鏈表

slowPre.next=None

returnslow

"""

方法功能:對不帶頭結點的單鏈表翻轉

輸入參數:head:鏈表頭結點

"""

defReverse(head):

ifhead==Noneorhead.next==None:

returnhead

pre=head#前驅結點

cur=head.next#當前結點

next=cur.next#后繼結點

pre.next=None

#使當前遍歷到的結點cur指向其前驅結點

whilecurisnotNone:

next=cur.next

cur.next=pre

pre=cur

cur=cur.next

cur=next

returnpre

"""

方法功能:對鏈表進行排序

輸入參數:head:鏈表頭結點

"""

defReorder(head):

ifhead==Noneorhead.next==None:

return

#前半部分鏈表第一個結點

cur1=head.next

mid=FindMiddleNode(head.next)

#后半部分鏈表逆序后的第一個結點

cur2=Reverse(mid)

tmp=None

#合并兩個鏈表

whilecur1.nextisnotNone:

tmp=cur1.next

cur1.next=cur2

cur1=tmp

tmp=cur2.next

cur2.next=cur1

cur2=tmp

cur1.next=cur2

if__name__="__main__":

i=1

head=LNode()

head.next=None

tmp=None

cur=head

#構造第一個鏈表

whilel＜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

Reorder(head)

print"\n排序后:",

cur=head.next

whilecur!=None:

printcur.data,

cur=cur.next

程序的運行結果為：

排序前：1234567

排序后：1726354

算法性能分析：

查找鏈表的中間結點的方法的時間復雜度為O(N)，逆序子鏈表的時間復雜度也為O(N)，合并兩個子鏈表的時間復雜度也為O(N)，因此，整個方法的時間復雜度為O(N)，其中，N表示的是鏈表的長度。由于這種方法只用了常數個額外指針變量，因此，空間復雜度為O(1)。[考點]如何對鏈表進行重新排序

5.

找出單鏈表中的倒數第k個元素，例如給定單鏈表：1-＞2-＞3-＞4-＞5-＞6-＞7，則單鏈表的倒數第k=3個元素為5。正確答案：方法一：順序遍歷兩遍法

主要思路：首先遍歷一遍單鏈表，求出整個單鏈表的長度n，然后把求倒數第k個元素轉換為求順數第n-k個元素，再去遍歷一次單鏈表就可以得到結果。但是該方法需要對單鏈表進行兩次遍歷。

方法二：快慢指針法

由于單鏈表只能從頭到尾依次訪問鏈表的各個結點，因此，如果要找鏈表的倒數第k個元素，也只能從頭到尾進行遍歷查找，在查找過程中，設置兩個指針，讓其中一個指針比另一個指針先前移k步，然后兩個指針同時往前移動。循環直到先行的指針值為None時，另一個指針所指的位置就是所要找的位置。程序代碼如下：

classLNode:

def__new__(self,x):

self.data=x

self.next=None

#構造一個單鏈表

defConstructList():

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

returnhead

#順序打印單鏈表結點的數據

defPrintList(head):

c