算法套路四——反转链表

算法套路四——反转链表

算法示例一：LeetCode206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

初始化pre为空，cur为头指针

pre指针：记录当前结点的前一个结点
cur指针：记录当前结点，cur的next指针指向pre
nxt指针：记录当前结点的后一个结点，记录cur的next，防止断链
循环中左边按照ncpc的顺序反转，右边按照cpcn的顺序，且左右两边第一个c都为cur.next

反转结束后，从原来的链表上看:pre指向反转这一段的末尾,cur指向反转这一段后续的下一个节点

class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre = Nonecur = headwhile cur:nxt = cur.nextcur.next = prepre = curcur = nxt#顺序为ncpcreturn pre

算法示例二：LeetCode92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

这题比前一题相比只是在中间进行反转，

• 如果left=1，那么反转的逻辑与前一题一样，可以令pre = None，cur = head
• 但若是left>1，我们在反转时不是从head开始，那么在反转后需要一个结点p0来记录反转的前一个结点，从而反转后可以连接到前面的结点

但分情况讨论在问题复杂时比较麻烦，所以我们可以用到反转链表时常用的哨兵dummy结点，它可以作为一个“假”的头结点，它的下一个结点指向真正的头结点head，这样的话就可以认为left无论是大于或是等于1，都可以用p0来记录反转前的结点

初始化后如图所示
pre指向null，p0指向反转前一个结点，

在反转结束后链表结构如下图所示：

因此直接令
p0.next.next=cur
p0.Next = pre
最后结果是

且最后返回dummy.next，不管head结点是否参与反转，dummy.next一定是指向反转后的链表头结点

func reverseBetween(head *ListNode, left int, right int) *ListNode {dummy := &ListNode{Val: 0, Next: head}p0:=dummyfor i:=1;i<left;i++{p0=p0.Next}var pre,cur *ListNode = nil, p0.Nextfor i:=0;i<right-left+1;i++{nxt:=cur.Nextcur.Next=prepre=curcur=nxt}p0.Next.Next = curp0.Next = prereturn dummy.Next
}

练习Leetcode25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

此题首先按照上一题的思路，在第一次反转后如图所示

之后进行下一次反转时如果按照上题的思路对p0进行移动 p0.Next.Next = cur p0.Next = pre,会得到如下图示

我们可以发现在进行转变后，对3，4进行反转时丢失了反转前一个节点，这样会导致之后的反转丢失前链，所以我们在转变之前需要一个变量pnext来记录p0.next，从而可以记录第二次反转的前一个结点指针，然后进行p0.Next.Next = cur、p0.Next = pre赋值后，再将pnext赋给p0
最后如上题一样返回dummy.next

func reverseKGroup(head *ListNode, k int) *ListNode {n:=0for node:=head;node!=nil;node=node.Next{n++}dummy := &ListNode{Val: 0, Next: head}var pre *ListNode=nilcur:=headp0:=dummyfor ;n>=k;n-=k{for i:=0;i<k;i++{nxt:=cur.Nextcur.Next=prepre=curcur=nxt}p0.Next.Next = curpnext:=p0.Next//记录p0.Next，防止断链p0.Next = prep0=pnext}return dummy.Next
}

练习LeetCode24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。