网站建设的经济可行性分析,免费公司网站如何建立设计,wordpress主题缓存,山东网站备案号算法套路四——反转链表
算法示例一#xff1a;LeetCode206. 反转链表 给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。 初始化pre为空#xff0c;cur为头指针
pre指针#xff1a;记录当前结点的前一个结点 cur指针#xff1a;记录当…算法套路四——反转链表
算法示例一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 的链表节点返回 反转后的链表 。 这题比前一题相比只是在中间进行反转
如果left1那么反转的逻辑与前一题一样可以令pre Nonecur head但若是left1我们在反转时不是从head开始那么在反转后需要一个结点p0来记录反转的前一个结点从而反转后可以连接到前面的结点
但分情况讨论在问题复杂时比较麻烦所以我们可以用到反转链表时常用的哨兵dummy结点它可以作为一个“假”的头结点它的下一个结点指向真正的头结点head这样的话就可以认为left无论是大于或是等于1都可以用p0来记录反转前的结点
初始化后如图所示 pre指向nullp0指向反转前一个结点
在反转结束后链表结构如下图所示
因此直接令 p0.next.nextcur 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;ileft;i{p0p0.Next}var pre,cur *ListNode nil, p0.Nextfor i:0;iright-left1;i{nxt:cur.Nextcur.Nextpreprecurcurnxt}p0.Next.Next curp0.Next prereturn dummy.Next
}练习Leetcode25. K 个一组翻转链表 给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。 此题首先按照上一题的思路在第一次反转后如图所示 之后进行下一次反转时如果按照上题的思路对p0进行移动 p0.Next.Next cur p0.Next pre,会得到如下图示 我们可以发现在进行转变后对34进行反转时丢失了反转前一个节点这样会导致之后的反转丢失前链所以我们在转变之前需要一个变量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;nodenode.Next{n}dummy : ListNode{Val: 0, Next: head}var pre *ListNodenilcur:headp0:dummyfor ;nk;n-k{for i:0;ik;i{nxt:cur.Nextcur.Nextpreprecurcurnxt}p0.Next.Next curpnext:p0.Next//记录p0.Next防止断链p0.Next prep0pnext}return dummy.Next
}练习LeetCode24. 两两交换链表中的节点 给你一个链表两两交换其中相邻的节点并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题即只能进行节点交换。
