第python反轉(zhuǎn)單鏈表算法題現(xiàn)在算法是大廠面試的必考題，而且越來越難，已經(jīng)不是簡(jiǎn)單的列表，字符串操作了，會(huì)涉及到各種數(shù)據(jù)結(jié)結(jié)構(gòu)。單鏈表的反轉(zhuǎn)也是經(jīng)常考的一道題，里面故在此記錄一下。

1.鏈表的特點(diǎn)：

順序存儲(chǔ)元素，但是元素在空間上是不連續(xù)的，所以在鏈表每個(gè)元素中除了存儲(chǔ)元素的值，還會(huì)存儲(chǔ)下一個(gè)元素的地址，單鏈表的話就只有指向下一個(gè)元素的指針，雙向鏈表的話還會(huì)有指向前一個(gè)元素的指針。正是由于鏈表以上的存儲(chǔ)特點(diǎn)，在做插入和刪除操作時(shí)只需要斷開指針的連接，不需要移動(dòng)后面的數(shù)據(jù)，所以對(duì)鏈表修改的效率會(huì)很高，但是查找的效率會(huì)很低，這也正是鏈表和數(shù)組的區(qū)別。鏈表的存儲(chǔ)示意圖：

完成這道題至少有3種方式：

1.先對(duì)原鏈表做頭部刪操作，再對(duì)新鏈表做頭部插入操作；

2.通過3個(gè)指針實(shí)現(xiàn)，p0指向前一個(gè)節(jié)點(diǎn)的指針，p1表示當(dāng)前節(jié)點(diǎn)的指針，p2表示下一個(gè)節(jié)點(diǎn)的指針

3.用遞歸實(shí)現(xiàn)；

2.方式一：

1)創(chuàng)建一個(gè)新的空列表；

2）取出舊鏈表中頭結(jié)點(diǎn)的元素，將其next指針設(shè)置為新鏈表的頭指針，同時(shí)將舊鏈表的頭結(jié)點(diǎn)執(zhí)行下一個(gè)元素

3）依次重復(fù)第2）步的操作，直到取出就鏈表中所有的節(jié)點(diǎn)。

4）最后形成的新鏈表如下，實(shí)現(xiàn)了反轉(zhuǎn)的功能：

5）代碼實(shí)現(xiàn)：

#encoding=utf-8

importcopy

classNode:

"""節(jié)點(diǎn)類，包含值和下一個(gè)節(jié)點(diǎn)的指針"""

def__init__(self,value,next=None):

self.value=value

self.next=next

def__str__(self):

return"Nodevalue:%s"%self.value

classLinkedList:

def__init__(self,head=None,tail=None):

self.head=head

self.tail=tail

defget_all(self):

"""獲取鏈表中所有的節(jié)點(diǎn)"""

nodes=[]

temp=self.head

whiletemp:

nodes.append(temp.value)

temp=temp.next

returnnodes

defadd_node(self,value):

"""在列表中添加節(jié)點(diǎn)"""

node=Node(value)

#空鏈表,收尾指針都指向新增加的節(jié)點(diǎn)

ifself.headisNone:

self.head=node

self.tail=node

else:

self.tail.next=node

self.tail=node

defreverse_list(self):

"""反轉(zhuǎn)單向列表

思路一：先對(duì)原鏈表做頭刪操作，再對(duì)新鏈表做頭插

"""

#定義一個(gè)新的鏈表

new_list_node=LinkedList()

temp=copy.deepcopy(self.head)

whiletemp:

#1.對(duì)之前的鏈表做頭刪除操作

node=temp

temp=temp.next

#2.對(duì)新的鏈表做頭插入操作

ifnew_list_node.headisNone:

new_list_node.tail=node

node.next=new_list_node.head

new_list_node.head=node

returnnew_list_node

if__name__=="__main__":

l=LinkedList()

foriinrange(5):

l.add_node(i)

new_list_node=l.reverse_list()

print(new_list_node.get_all())

print(new_list_node.tail)

3.方式二

借助3個(gè)指針來實(shí)現(xiàn)反轉(zhuǎn)，p0之前前一個(gè)節(jié)點(diǎn)，p1指向當(dāng)前操作的節(jié)點(diǎn)，p2指向下一個(gè)節(jié)點(diǎn)。操作過程如下：將p1的next指針之前p0，之后將p0指向p1節(jié)點(diǎn)，p1指向p2節(jié)點(diǎn)，如果p1不為空，重復(fù)以上操作，最后，p0即為新列表的頭節(jié)點(diǎn)。

1）開始時(shí)p0為空；將p1指向鏈表的頭節(jié)點(diǎn)，p1節(jié)點(diǎn)的next指針指向p0；p2指向下一個(gè)節(jié)點(diǎn)：

2）調(diào)整3個(gè)指針的指向：將p0指向p1；p1指向p2，p1的next指向p0；p2指向下一個(gè)節(jié)點(diǎn)

3）循環(huán)執(zhí)行以上步驟，直到p1指向的節(jié)點(diǎn)不為空，最后得到的鏈表為：

4）代碼實(shí)現(xiàn)：

#encoding=utf-8

importcopy

classNode:

"""節(jié)點(diǎn)類，包含值和下一個(gè)節(jié)點(diǎn)的指針"""

def__init__(self,value,next=None):

self.value=value

self.next=next

def__str__(self):

return"Nodevalue:%s"%self.value

classLinkedList:

def__init__(self,head=None,tail=None):

self.head=head

self.tail=tail

defget_all(self):

"""獲取鏈表中所有的節(jié)點(diǎn)"""

nodes=[]

temp=self.head

whiletemp:

nodes.append(temp.value)

temp=temp.next

returnnodes

defadd_node(self,value):

"""在列表中添加節(jié)點(diǎn)"""

node=Node(value)

#空鏈表,收尾指針都指向新增加的節(jié)點(diǎn)

ifself.headisNone:

self.head=node

self.tail=node

else:

self.tail.next=node

self.tail=node

defreverse_list(self):

"""

反轉(zhuǎn)單向列表

思路二：通過3個(gè)指針實(shí)現(xiàn)，p0指向前一個(gè)節(jié)點(diǎn)的指針，p1表示當(dāng)前節(jié)點(diǎn)的指針，p2表示下一個(gè)節(jié)點(diǎn)的指針

:return:LinkedList對(duì)象

"""

p1=copy.deepcopy(self.head)

p2=p1.next

#定義一個(gè)新的鏈表對(duì)象

new_list_node=LinkedList()

whilep1:

ifnew_list_node.headisNone:

new_list_node.tail=p1

#將p1的next指向新鏈表的頭結(jié)點(diǎn)

p1.next=new_list_node.head

#將新鏈表的頭結(jié)點(diǎn)指向p1

new_list_node.head=p1

#將p1指向p2

p1=p2

#判斷p2是否指向了鏈表的末尾

ifp2:

p2=p2.next

returnnew_list_node

if__name__=="__main__":

l=LinkedList()

foriinrange(5):

l.add_node(i)

new_list_node=l.reverse_list()

print(new_list_node.get_all())

print(new_list_node.tail)

4.方式三：

遞歸就是將問題分解為處理過程一致的子問題進(jìn)行處理，但是一定要要結(jié)束條件。鏈表的反轉(zhuǎn)也可以采用遞歸的方式實(shí)現(xiàn)，每次傳入的節(jié)點(diǎn)不是最后一個(gè)的話，就將下一個(gè)節(jié)點(diǎn)作為參數(shù)傳遞進(jìn)去，遞歸調(diào)用；直到傳入的是最后一個(gè)節(jié)點(diǎn)時(shí)開始逐級(jí)返回。

1）將鏈表中每個(gè)節(jié)點(diǎn)作為參數(shù)，依次傳入到reverse_list函數(shù)中；

2）當(dāng)傳入的是最后一個(gè)節(jié)點(diǎn)時(shí)，以此節(jié)點(diǎn)為頭結(jié)點(diǎn)創(chuàng)建一個(gè)新的鏈表，并將此鏈表返回；

3）上一級(jí)的調(diào)用者接受到返回的鏈表后，將傳入的節(jié)點(diǎn)作為鏈表的尾結(jié)點(diǎn)放到鏈表中；

4）逐級(jí)返回，直到回到最開始執(zhí)行reverse_list函數(shù)中，將生成的新鏈表返回即可

5）代碼實(shí)現(xiàn)：

#encoding=utf-8

importcopy

classNode:

"""節(jié)點(diǎn)類，包含值和下一個(gè)節(jié)點(diǎn)的指針"""

def__init__(self,value,next=None):

self.value=value

self.next=next

def__str__(self):

return"Nodevalue:%s"%self.value

classLinkedList:

def__init__(self,head=None,tail=None):

self.head=head

self.tail=tail

defget_all(self):

"""獲取鏈表中所有的節(jié)點(diǎn)"""

nodes=[]

temp=self.head

whiletemp:

nodes.append(temp.value)

temp=temp.next

returnnodes

defadd_node(self,value):

"""在列表中添加節(jié)點(diǎn)"""

node=Node(value)

#空鏈表,收尾指針都指向新增加的節(jié)點(diǎn)

ifself.headisNone:

self.head=node

self.tail=node

else:

self.tail.next=node

self.tail=node

defreverse_list(self,node):

"""

反轉(zhuǎn)單鏈表

思路三：用遞歸實(shí)現(xiàn)

:return:LinkedList對(duì)象

"""

ifnode.nextisNone:

returnLinkedList(node,node)

temp=copy.deepcopy(node)

#斷開當(dāng)前節(jié)點(diǎn)的連接

temp.next=None

#將當(dāng)前節(jié)點(diǎn)放到內(nèi)層遞歸返回的鏈表結(jié)尾

l=self.reverse_list(node.next)