Python程序員面試分類真題2

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

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

（分數(shù)：16.50）__________________________________________________________________________________________

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

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

方法二：就地逆序

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

在上圖中，當前遍歷到結(jié)點cur，通過(1)～(6)6個步驟用虛線的指針來代替實線的指針實現(xiàn)相鄰結(jié)點的逆序。其中，(1)～(4)實現(xiàn)了前兩個結(jié)點的逆序操作，(5)和(6)兩個步驟向后移動指針，接著可以采用同樣的方式實現(xiàn)后面兩個相鄰結(jié)點的逆序操作。實現(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#當前遍歷結(jié)點

pre=head#當前結(jié)點的前驅(qū)結(jié)點

next=None#當前結(jié)點后繼結(jié)點的后繼結(jié)點

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

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

順序輸出：1234567

逆序輸出：2143657

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

算法性能分析：

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

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

（分數(shù)：16.50）__________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

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

classLNode:

def__new__(self,x):

self.data=x

self.next=None

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

defReverse(head):

ifhead==Noneorhead.next==None:

returnhead

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

cur=head.next#當前結(jié)點

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

pre.next=None

#使當前遍歷到的結(jié)點cur指向其前驅(qū)結(jié)點

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個結(jié)點

whilei＜k:

ifend.next!=None:

end=end.next

else:#剩余結(jié)點的個數(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

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

順序輸出：1234567

逆序輸出：3216547

運行結(jié)果分析：

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

算法性能分析：

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

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

（分數(shù)：16.50）__________________________________________________________________________________________

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

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

由于鏈表按升序排列，首先通過比較鏈表第一個結(jié)點中元素的大小來確定最終合并后鏈表的頭結(jié)點；接下來每次都找兩個鏈表中剩余結(jié)點的最小值鏈接到被合并的鏈表后面，如上圖中的虛線所示。具體實現(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

"""

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

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

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

"""

defMerge(head1,head2):

ifhead1==Noneorhead1.next==None:

returnhead2

ifhead2==Noneorhead2.next==None:

returnhead1

cur1=head1.next#用來遍歷head1

cur2=head2.next#用來遍歷head2

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

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

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

ifcur1.data＞cur2.data:

head=head2

cur=cur2

cur2=cur2.next

else:

head=head1

cur=cur1

cur1=cur1.next

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

whilecur1!=Noneandcur2!=None:

ifcur1.data＜cur2.data:

cur.next=cur1

cur=cur1

cur1=cur1.next

else:

cur.next=cur2

cur=cur2

cur2=cur2.next

#當遍歷完一個鏈表后把另外一個鏈表剩余的結(jié)點鏈接到合并后的鏈表后面

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)

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

head1:1

3

5

head2:2

4

6

合并后的鏈表：123456

算法性能分析：

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

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

（分數(shù)：16.50）__________________________________________________________________________________________

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

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

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

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

在上圖中，首先把結(jié)點p的后繼結(jié)點的數(shù)據(jù)復(fù)制到結(jié)點p的數(shù)據(jù)域中；接著把結(jié)點p的后繼結(jié)點刪除。實現(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

"""

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

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

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

"""

defRemoveNode(p):

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

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é)點

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é)點"+str(p.data)+"前鏈表:",

printList(head)

result=RemoveNode(p)

ifresult:

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

printList(head)

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

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

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

算法性能分析：

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

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

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

（分數(shù)：16.50）__________________________________________________________________________________________

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

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

算法性能分析：

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

方法二：首尾相接法

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

方法三：尾結(jié)點法

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

classLNode:

def__new__(self,x):

self.data=x

self.next=None

"""

方法功能:判斷兩個鏈表是否相交,如果相交找出交點

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

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

"""

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é)點,同時記錄head1的長度

whiletemp1.next!=None:

temp1=temp1.next

n1+=1

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

whiletemp2.next!=None:

temp2=temp2.next

n2+=1

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

iftemp1==temp2:

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

ifn1＞n2:

whilen1-n2＞0:

head1=head1.next

n1-=1

ifn2＞n1:

whilen2-n1＞0:

head2=head2.next

n2==1

#兩個鏈表同時前進,找出相同的結(jié)點

whilehead1!=head2:

head1=head1.next

head2=head2.next

returnhead1

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

else:

returnNone

if__name__="__main__":

i=1

#鏈表頭結(jié)點

head1=LNode()

head1.next=None

#鏈表頭結(jié)點

head2=LNode()

head2.next=None

tmp=None

cur=head1

p=None

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

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個鏈表

i=1

whilei＜5:

tmp=LNode()

tmp.data=i

tmp.next=None

cur.next=tmp

cur=tmp

i+=1

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

cur.next=p

interNode=IsIntersect(head1,head2)

ifinterNode==None:

print"這兩個鏈表不相交:"

else:

print"這兩個鏈表相交點為:"+str(interNode.data)

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

這兩個鏈表相交點為：5

運行結(jié)果分析：

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

算法性能分析：

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

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

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

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

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

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

（分數(shù)：17.50）__________________________________________________________________________________________

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

#用來合并兩個有序的鏈表*

defmerge(self,a,b):

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

ifa==None:

returnb

ifb==None:

returna

#把兩個鏈表頭中較小的結(jié)點賦值給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