代码随想录算法训练营第四天 | Leetcode 24.两两交换链表中的节点 | 19.删除链表的倒数第N个节点 | 面试题 02.07. 链表相交 | 142.环形链表 II

24.两两交换链表中的节点力扣题目链接24. 两两交换链表中的节点 - 力扣LeetCode文章讲解24. 两两交换链表中的节点 | 链表 | 虚拟头结点 | 节点交换 | 代码随想录视频讲解帮你把链表细节学清楚 | LeetCode24. 两两交换链表中的节点_哔哩哔哩_bilibili/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */publicclassSolution{publicListNodeSwapPairs(ListNodehead){ListNodevheadnewListNode();vhead.nexthead;ListNodecurvhead;while(cur.next!nullcur.next.next!null){//不能交换两个条件的顺序//交换ListNodetmpcur.next;cur.nextcur.next.next;tmp.nextcur.next.next;cur.next.nexttmp;//移动curcurtmp;//cur cur.next.next;}returnvhead.next;}}时间复杂度O(n)空间复杂度O(1)交换过程如图注意操作的指针一定要在交换的两个节点的前一个节点ps: 做这样的题一定自己画一下图理解干想太难了画图就很简单了 (°O°)19.删除链表的倒数第N个节点力扣题目链接19. 删除链表的倒数第 N 个结点 - 力扣LeetCode文章讲解19.删除链表的倒数第N个节点 | 双指针 | 虚拟头节点 | 代码随想录视频讲解链表遍历学清楚 | LeetCode19.删除链表倒数第N个节点_哔哩哔哩_bilibili注意到题目规定的是单链表使用双指针思想完成让快指针比慢指针快n1个节点当快指针移动到节点最后的null的时候慢指针的后一个节点是目标节点/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val0, ListNode nextnull) { * this.val val; * this.next next; * } * } */publicclassSolution{publicListNodeRemoveNthFromEnd(ListNodehead,intn){ListNodevheadnewListNode();vhead.nexthead;ListNodelowNodevhead;ListNodefastNodevhead;//找到需要删除的节点位置while(n0){fastNodefastNode.next;n--;}//达成fastindex在lowindex之后n 1个位置while(fastNode!null){fastNodefastNode.next;lowNodelowNode.next;}//lowNode节点的后一个节点即需要删除节点ListNodetmplowNode.next;//删除操作lowNode.nextlowNode.next.next;//让gc释放删除的节点tmp.nextnull;returnvhead.next;//这里不要return head因为head可能是被删除的节点;}}时间复杂度O(n)空间复杂度O(1) (°O°)面试题 02.07. 链表相交力扣题目链接面试题 02.07. 链表相交文章讲解双指针技巧链表相交问题力扣 160 链表相交 | 代码随想录思路先让两个链表的剩余部分一样长然后同时移动做判断/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val x; } * } */publicclassSolution{publicListNodeGetIntersectionNode(ListNodeheadA,ListNodeheadB){ListNodecopyAheadA;ListNodecopyBheadB;intcountA0;intcountB0;//判断两个链表各自的长短while(copyA!null){copyAcopyA.next;countA;}while(copyB!null){copyBcopyB.next;countB;}intoffsetMath.Abs(countB-countA);//判断是哪个长移动对应头节点if(countBcountA){while(offset0){headBheadB.next;offset--;}}else{while(offset0){headAheadA.next;offset--;}}//遍历找交叉节点while(headA!headB){headAheadA.next;headBheadB.next;if(headAnull||headBnull){returnnull;//如果没有交叉}}returnheadA;}}时间复杂度O(n)空间复杂度O(1)附加因为题目中说val的值是大于1的所以可以遍历AB中任意一条链表将其中的数据改为负数再让从另一条链表遍历碰到的第一个值为负数的链表即为交叉起点(°O°)(°O°)(°O°)142.环形链表 II力扣题目链接142. 环形链表 II文章讲解142.环形链表II | 快慢指针 | 环入口查找 | 代码随想录视频讲解把环形链表讲清楚 如何判断环形链表如何找到环形链表的入口 LeetCode142.环形链表II_哔哩哔哩_bilibili思路首先想到把每个节点都存下来遍历直到有相同节点出现返回该节点但空间复杂度为O(n)时间复杂度为O(n)空间复杂度为O(1)的写法分析过程复杂可以看看文章讲解publicclassSolution{publicListNodeDetectCycle(ListNodehead){ListNodefasthead;ListNodeslowhead;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;if(fastslow)//这个条件说明有环{fasthead;while(fast!slow)//让两个指针分别从相遇位置和链表头节点开始走都每次走一个节点两个指针相遇位置即循环起点{fastfast.next;slowslow.next;}returnfast;}}returnnull;}}‍链表篇总结链表总结篇 | 虚拟头结点 | 双指针法 | 反转链表 | 代码随想录