[代码随想录Day4打卡] 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II 总结

24. 两两交换链表中的节点

题目：
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

重点：

1. 明确具体交换怎么做。交换其中1，2节点的示意图如下所示，总共有三步。但是在进行步骤一的时候会丢失cur->next的值，进行步骤2会丢失cur->next->next->next的值，进行步骤三虽然会丢失cur->next->next的值但是这个值我们是在第一步使用不是在后面步骤中使用，所以已经把它放到相应位置了。总体来说我们需要保存cur->next值和cu->next->next->next这两个节点。
   所以伪代码如下：

temp = cur.next;
temp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = temp;
temp->next = temp1;
cur = cur->next->next;//移动两步

2. 明确循环的结束条件。对于链表长度为偶数的话，就是$cur->next==Null$，对于链表长度为奇数的，就是$cur->next->next==Null$。所以终止条件是$cur->next==None||cur->next->next==Null$，转换成程序就是while(cur->next!=Null && cur->next->next!=Null):
明确上面两个步骤就好写了，为了操作统一加上虚拟头节点。
下面是JAVA和Python代码：

class Solution {public ListNode swapPairs(ListNode head) {//建立虚拟头节点ListNode dummyhead = new ListNode(-1);dummyhead.next = head;ListNode cur = dummyhead;while(cur.next!=null && cur.next.next!=null){ListNode temp = cur.next;ListNode temp1 = cur.next.next.next;cur.next = cur.next.next;cur.next.next = temp;temp.next = temp1;cur = temp;}return dummyhead.next;}
}

class Solution(object):def swapPairs(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""dummy_head = ListNode(next=head)#设置虚拟头节点cur = dummy_headwhile(cur.next!=None and cur.next.next != None):temp = cur.nexttemp1 = cur.next.next.next#保存下一个节点和下下个节点cur.next = cur.next.nextcur.next.next = temptemp.next = temp1cur = tempreturn dummy_head.next

19.删除链表的倒数第N个节点

重点：删除链表中一个节点的时候需要定位到该节点的上一个节点。
思路：使用双指针，一个快指针一个慢指针，快指针先移动n+1步（为了获得被删除节点的前一个节点），然后快慢指针一起向前移动。
删除操作就是:slow->next = slow->next->next。（就把slow->next删除了，即被删除节点）

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyhead = new ListNode(-1);dummyhead.next = head;ListNode fast = dummyhead;ListNode slow = dummyhead;n++;while(n>0 && fast != null ){fast = fast.next;n--;}while(fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;//删除指针的操作return dummyhead.next;}
}

class Solution(object):def removeNthFromEnd(self, head, n):""":type head: Optional[ListNode]:type n: int:rtype: Optional[ListNode]"""dummyhead = ListNode(-1)dummyhead.next = headn+=1fast = dummyheadslow = dummyheadwhile(n>0 and fast!=None):fast = fast.next#先移动N+1步n-=1while(fast!=None):fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummyhead.next

面试题 02.07. 链表相交

重点：

1. 是链表相等，不是值相等listnode1==listnode2就可以直接return listnode1(listnode2也可以)。
2. 链表相交就是末尾的node都相同，需要末尾对齐，需要知道两个链表的长度。（刚开始一头雾水，后来看讲解明白了。）
   看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
   
   我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图：
   
   此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

否则循环退出返回空指针。

PS:这个解释就直接抄代码随想录上的了。（(●’◡’●)）

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode curA = headA;ListNode curB = headB;int lenA = 0, lenB = 0;while(curA != null){lenA++;//求链表A的长度curA = curA.next;}while(curB != null){lenB++;curB = curB.next;}curA = headA;curB = headB;if(lenB > lenA){int tmpLen = lenA;lenA = lenB;lenB = tmpLen;ListNode tmpNode = curA;curA = curB;curB = tmpNode;}//交换是为了让A永远是长度最大的方便后续统一进行操作//求长度差int gap = lenA-lenB;//让curA和curB在同一起点上（末尾位置对齐）while(gap-->0){curA = curA.next;}//遍历curA和curB，遇到相同的则之间返回while(curA != null){if(curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}
}

下面这个可以想象两个列表长度不相同，那么就是其中指针A先遍历完短的链表之后，再到长链表中，当指针B遍历完长的链表到短的链表上的时候，两个链表就实现了末尾对齐。（A指针在长链表的倒数len(短链表)的位置）

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//方法二合并链表ListNode p1 = headA, p2 = headB;while(p1!=p2){//p1走一步，如果走到A链表的末尾，转换到B链表//极端情况就是A,B没有交点，而且长度不相等，p1和p2走完两个链表if(p1==null) p1 = headB;else p1 = p1.next;//p2也是，如果走到B链表的末尾就转换到A链表if(p2 == null) p2 = headA;else p2 = p2.next;}return p1;//p2也可以}
}

Python有不同的方法，我感觉思想应该相同就只看了一个。

class Solution(object):def getIntersectionNode(self, headA, headB):""":type head1, head1: ListNode:rtype: ListNode"""#求长度，同时出发lenA, lenB = 0, 0cur = headAwhile cur:cur = cur.nextlenA += 1cur = headBwhile cur:cur = cur.nextlenB += 1curA, curB = headA, headBif lenA > lenB:curA, curB = curB, curAlenA, lenB = lenB, lenA for _ in range(lenB - lenA): #让母后curA金额curB在末尾位置对齐curB = curB.nextwhile curA:if curA == curB:return curAelse:curA = curA.nextcurB = curB.nextreturn None

142.环形链表II

需要数学推导。
重点：

1. 判断有环：定义快慢指针，快指针每次移动两步，慢指针每次移动一步（两者相对速度为1），如果快慢指针相遇说明有环。
2. 找到环的入口：两个指针从头节点和快慢指针相遇的地方同时移动，交点就是环形入口节点，视频很详细，需要数学推导。
   
   JAVA和Python代码如下：

public class Solution {public ListNode detectCycle(ListNode head) {//快慢指针ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){fast = fast.next.next;//k快指针每次移动两步，慢指针每次移动一步，这样相对速度是1，一定可以在环内相遇slow = slow.next;if(fast == slow){ListNode index1 = fast;ListNode index2 = head;while(index1 != index2){index1 = index1.next;index2 = index2.next;}return index1;}}return null;}
}

class Solution(object):def detectCycle(self, head):""":type head: ListNode:rtype: ListNode"""#下面这个是我根据伪代码写的fast = headslow = headwhile(fast!=None and fast.next!=None):fast = fast.next.nextslow = slow.nextif(fast == slow):#找到相遇点说明有环，找环的入口index1 = fast#相遇点index2 = headwhile(index1!= index2):index1 = index1.nextindex2 = index2.nextreturn index1return None

总结

我感觉对链表节点进行操作的话，使用虚拟头节点可以统一操作。
然后链表交换位置，改变顺序，一定记得断开一个连接（也就是对next节点赋值的时候），也会丢失一些信息，为了防止信息丢失，需要定义临时节点来存储。
双指针思想，还是很好用。
要求返回链表的话就是返回头指针。

参考的题目、文章、视频

1. https://leetcode.cn/problems/swap-nodes-in-pairs/description/
2. https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
3. https://www.bilibili.com/video/BV1YT411g7br/
4. https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
5. https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
6. https://www.bilibili.com/video/BV1vW4y1U7Gf/?vd_source=145b0308ef7fee4449f12e1adb7b9de2
7. https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/
8. https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
9. https://leetcode.cn/problems/linked-list-cycle-ii/description/
10. https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
11. https://www.bilibili.com/video/BV1if4y1d7ob/
12. https://www.programmercarl.com/%E9%93%BE%E8%A1%A8%E6%80%BB%E7%BB%93%E7%AF%87.html