鏈表是一種基礎的數據結構，也是算法學習的重中之重。其中單鏈表反轉是一個經常會被考察到的知識點。

單鏈表反轉是將一個給定順序的單鏈表通過算法轉為逆序排列，盡管聽起來很簡單，但要通過算法實現也并不是非常容易。現在來給大家簡單介紹一下單鏈表反轉算法實現的基本原理和python代碼實現。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?算法基本原理及python代碼
1、方法一：三個指針遍歷反轉
算法思想：使用3個指針遍歷單鏈表，逐個鏈接點進行反轉。

?

（1）分別用p,q兩個指針指定前后兩個節點。其中p.next = q

?

（2）將p指針指向反方向。

?

（3）將q指針指向p。q.next = p，同時用r代表剩余未反轉節點。

?

（4）將p,q指針同時后移一位，回到步驟（2）的狀態。

?

（5）r指針指向剩余未反轉節點。循環執行（3）之后的操作。

# 詳細版
def reverse01(head):
if head == None:
return None
# 分別用p,q兩個指針指定先后兩個節點
p = head
q = head.next

# 將p節點反轉，head節點只能指向None
p.next = None

# 當存在多個后續節點時，循環執行
while q:
r = q.next # 用r表示后面未反轉節點
q.next = p # q節點反轉指向p
p = q
q = r # p,q節點后移一位，循環執行后面的操作

return p

# 精簡版
def reverse01(head):
if not head:
return None
p,q,p.next = head,head.next,None
while q:
q.next,p,q = p,q,q.next
return p
2、方法二：尾插法反轉
算法思想：固定頭節點，然后將后面的節點從前到后依此插入到次節點的位置，最后再將頭節點移動到尾部。

?

# 詳細版
def reverse02(head):
# 判斷鏈表的節點個數
if head == None or head.next == None:
return head

p = head.next
# 循環反轉
while p.next:
q = p.next
p.next = q.next
q.next = head.next
head.next = q

# 將頭節點移動到尾部
p.next = head
head = head.next
p.next.next = None

return head

# 精簡版
def reverse02(head):
if not head or not head.next:
return head
p = head.next
while p.next:
q = p.next
p.next,q.next,head.next = q.next,head.next,q
p.next,head,p.next.next = head,head.next,None
return head
3、方法三：遞歸方式反轉
算法思想：把單鏈表的反轉看作頭節點head和后續節點head.next之間的反轉，循環遞歸。

?

?

?

?

def reverse03(head):
if head.next == None:
return head

new_head = reverse03(head.next)
head.next.next = head
head.next = None

return new_head
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? leetcode精簡代碼示例
?單鏈表的反轉邏輯思路比較清晰，因此關于單鏈表反轉重在考查代碼的經精簡度，而Python可以實現代碼的極度簡化，如下：

def reverse04(head):
curr,pre = head,None
while curr:
curr.next,pre,curr = pre,curr,curr.next
return pre
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??leetcode相關算法習題（92.反轉鏈表II）
利用以上算法思想完成leetcode習題：92.反轉鏈表II

習題描述：

反轉從位置?m?到?n?的鏈表。請使用一趟掃描完成反轉。

說明:
1 ≤?m?≤?n?≤ 鏈表長度。

# 算法思想：采用尾插法反轉思想（方法二）

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None

class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
root = ListNode(0)
root.next = head
Head = root # 指定一個頭部變量（方法二中固定的head）

for i in range(m-1):
Head = Head.next

if Head.next == None:
return head

pre = Head.next
while pre.next and m < n:
curr = pre.next
pre.next = curr.next
curr.next = Head.next
Head.next = curr
m += 1

# 由于m之前的元素不需要反轉，因此用root.next代替方法二中的head
return root.next

?

轉載于:https://www.cnblogs.com/ellisonzhang/p/11278910.html

總結

以上是生活随笔為你收集整理的单链表反转的原理和python代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。