算法套路四——反转链表
算法示例一: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 = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
#顺序为ncpc
return 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:=dummy
for i:=1;i<left;i++{
p0=p0.Next
}
var pre,cur *ListNode = nil, p0.Next
for i:=0;i<right-left+1;i++{
nxt:=cur.Next
cur.Next=pre
pre=cur
cur=nxt
}
p0.Next.Next = cur
p0.Next = pre
return 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:=0
for node:=head;node!=nil;node=node.Next{
n++
}
dummy := &ListNode{Val: 0, Next: head}
var pre *ListNode=nil
cur:=head
p0:=dummy
for ;n>=k;n-=k{
for i:=0;i<k;i++{
nxt:=cur.Next
cur.Next=pre
pre=cur
cur=nxt
}
p0.Next.Next = cur
pnext:=p0.Next//记录p0.Next,防止断链
p0.Next = pre
p0=pnext
}
return dummy.Next
}
练习LeetCode24. 两两交换链表中的节点
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。