单链表反转的原理和python代码实现

链表是一种基础的数据结构，也是算法学习的重中之重。其中单链表反转是一个经常会被考察到的知识点。

单链表反转是将一个给定顺序的单链表通过算法转为逆序排列，尽管听起来很简单，但要通过算法实现也并不是非常容易。现在来给大家简单介绍一下单链表反转算法实现的基本原理和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

巴特西

单链表反转的原理和python代码实现

最新文章

热门文章