单链表反转的原理和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 p2、方法二：尾插法反转算法思想：固定头节点，然后将后面的节点从前到后依此插入到次节点的位置，最后再将头节点移动到尾部。

# 详细版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 head3、方法三：递归方式反转算法思想：把单链表的反转看作头节点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