【完虐算法】反转链表【完虐算法】反转链表

反转链表 LeetCode206. 反转链表
问题描述

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。示例: 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]

分析问题
首先，我们按照题目的要求，先把图画出来，然后再分析。

文章图片

从图中我们可以看到，反转前和反转后指针的指向发生了反转。所以，我们在实现的过程中，我们可以通过调整链表的指针来达到反转链表的目的。

我们定义两个指针pre和cur。pre表示已反转部分的头结点，cur表示还没有反转部分的头结点。开始时cur=head，pre=None
每次让cur->next=pre，实现一次局部反转。
局部反转完成后，cur和pre同时向前移动一位。
循环上述过程，直到链表反转完成。

文章图片

代码实现

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def reverse(self, head): cur = head #初始化时，pre为None pre = None while cur: next=cur.next cur.next = pre pre = cur cur = next return prehead=ListNode(1,None) cur=head for i in range(2,6): tmp=ListNode(i,None) cur.next=tmp cur=cur.nexts=Solution() pre=s.reverse(head)while pre!=None: print(pre.val) pre=pre.next

【【完虐算法】反转链表】更多算法题解，关注公众号《程序员学长》，欢迎加入。