代码随想录算法训练营第四天 | Leetcode 24.两两交换链表中的节点 | 19.删除链表的倒数第N个节点 | 面试题 02.07. 链表相交 | 142.环形链表 II
24.两两交换链表中的节点
- 力扣题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）
- 文章讲解：24. 两两交换链表中的节点 | 链表 | 虚拟头结点 | 节点交换 | 代码随想录
- 视频讲解：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */publicclassSolution{publicListNodeSwapPairs(ListNodehead){ListNodevhead=newListNode();vhead.next=head;ListNodecur=vhead;while(cur.next!=null&&cur.next.next!=null){//不能交换两个条件的顺序！//交换ListNodetmp=cur.next;cur.next=cur.next.next;tmp.next=cur.next.next;cur.next.next=tmp;//移动curcur=tmp;//cur = cur.next.next;}returnvhead.next;}}时间复杂度O(n)，空间复杂度O(1)
交换过程如图：
注意：操作的指针一定要在交换的两个节点的前一个节点
ps: 做这样的题一定自己画一下图理解，干想太难了，画图就很简单了 <(°O°)>
19.删除链表的倒数第N个节点
力扣题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
文章讲解：19.删除链表的倒数第N个节点 | 双指针 | 虚拟头节点 | 代码随想录
视频讲解：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili
注意到题目规定的是单链表
使用双指针思想完成，让快指针比慢指针快n+1个节点，当快指针移动到节点最后的null的时候慢指针的后一个节点是目标节点
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int val=0, ListNode next=null) { * this.val = val; * this.next = next; * } * } */publicclassSolution{publicListNodeRemoveNthFromEnd(ListNodehead,intn){ListNodevhead=newListNode();vhead.next=head;ListNodelowNode=vhead;ListNodefastNode=vhead;//找到需要删除的节点位置while(n>=0){fastNode=fastNode.next;n--;}//达成fastindex在lowindex之后n + 1个位置while(fastNode!=null){fastNode=fastNode.next;lowNode=lowNode.next;}//lowNode节点的后一个节点即需要删除节点ListNodetmp=lowNode.next;//删除操作lowNode.next=lowNode.next.next;//让gc释放删除的节点tmp.next=null;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){ListNodecopyA=headA;ListNodecopyB=headB;intcountA=0;intcountB=0;//判断两个链表各自的长短while(copyA!=null){copyA=copyA.next;countA++;}while(copyB!=null){copyB=copyB.next;countB++;}intoffset=Math.Abs(countB-countA);//判断是哪个长，移动对应头节点if(countB>countA){while(offset>0){headB=headB.next;offset--;}}else{while(offset>0){headA=headA.next;offset--;}}//遍历找交叉节点while(headA!=headB){headA=headA.next;headB=headB.next;if(headA==null||headB==null){returnnull;//如果没有交叉}}returnheadA;}}时间复杂度O(n)，空间复杂度O(1)
附加：因为题目中说val的值是大于1的，所以可以遍历AB中任意一条链表将其中的数据改为负数，再让从另一条链表遍历，碰到的第一个值为负数的链表即为交叉起点
<(°O°)><(°O°)><(°O°)>
142.环形链表 II
- 力扣题目链接：142. 环形链表 II
- 文章讲解：142.环形链表II | 快慢指针 | 环入口查找 | 代码随想录
- 视频讲解：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili
思路：首先想到把每个节点都存下来，遍历直到有相同节点出现返回该节点，但空间复杂度为O(n)
时间复杂度为O(n)，空间复杂度为O(1)的写法：（分析过程复杂，可以看看文章讲解）
publicclassSolution{publicListNodeDetectCycle(ListNodehead){ListNodefast=head;ListNodeslow=head;while(fast!=null&&fast.next!=null){slow=slow.next;fast=fast.next.next;if(fast==slow)//这个条件说明有环{fast=head;while(fast!=slow)//让两个指针分别从相遇位置和链表头节点开始走，都每次走一个节点，两个指针相遇位置即循环起点{fast=fast.next;slow=slow.next;}returnfast;}}returnnull;}}