代码随想录第四天 | 链表part02

• 两两交换链表中的节点
  用虚拟头结点，这样会方便很多。
  本题链表操作就比较复杂了，建议大家先看视频，视频里我讲解了注意事项，为什么需要temp保存临时节点。
  题目链接/文章讲解/视频讲解： https://programmercarl.com/0024.两两交换链表中的节点.html
  

题目感想：
1.面对链表的题目为了方便处理，定义一个虚拟头节点，大概的思路就是，先让指针指向当前节点的NEXT节点,先保存NEXT节点的原始NEXT节点，然后使得NEXT节点的NEXT为它的前置节点，这样1、2节点的位置就替换过来了，然后cur指针再指向刚刚保存的那个节点，开始下一步操作；

1. public ListNode swapPairs(ListNode head) {
2.         ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
3.         dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
4.         ListNode cur = dumyhead;
5.         ListNode temp; // 临时节点，保存两个节点后面的节点
6.         ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
7.         ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
8.         while (cur.next != null && cur.next.next != null) {
9.             temp = cur.next.next.next;
10.             firstnode = cur.next;
11.             secondnode = cur.next.next;
12.             cur.next = secondnode;       // 步骤一
13.             secondnode.next = firstnode; // 步骤二
14.             firstnode.next = temp;      // 步骤三
15.             cur = firstnode; // cur移动，准备下一轮交换
16.         }
17.         return dumyhead.next;
18.     }
20. // 将步骤 2,3 交换顺序，这样不用定义 temp 节点
21. public ListNode swapPairs(ListNode head) {
22.     ListNode dummy = new ListNode(0, head);
23.     ListNode cur = dummy;
24.     while (cur.next != null && cur.next.next != null) {
25.         ListNode node1 = cur.next;// 第 1 个节点
26.         ListNode node2 = cur.next.next;// 第 2 个节点
27.         cur.next = node2; // 步骤 1
28.         node1.next = node2.next;// 步骤 3
29.         node2.next = node1;// 步骤 2
30.         cur = cur.next.next;
31.     }
32.     return dummy.next;
33. }

复制代码

2.还有一种方法是使用递归，先通过递归抵达链表末尾，递归回去的时候，就进行交换

1.     public ListNode swapPairs(ListNode head) {
2.         // base case 退出提交
3.         if(head == null || head.next == null) return head;
4.         // 获取当前节点的下一个节点
5.         ListNode next = head.next;
6.         // 进行递归
7.         ListNode newNode = swapPairs(next.next);
8.         // 这里进行交换
9.         next.next = head;
10.         head.next = newNode;
12.         return next;
13.     }

复制代码

19.删除链表的倒数第N个节点
双指针的操作，要注意，删除第N个节点，那么我们当前遍历的指针一定要指向 第N个节点的前一个节点，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0019.删除链表的倒数第N个节点.html
题目感想：
1.这里也定义虚拟头节点，然后通过快慢指针，因为要删除倒数的第N个节点，也就是距离尾部的距离为N的节点，所以我们先定义两个指针，快指针要先于慢指针走N个节点，然后两个节点再一起走，直到快指针抵达链表末尾；
2.需要注意定义了虚拟头节点的影响，以及快指针和慢指针之间的距离，慢指针停留下来要在想要删除节点的前面，这样才能便于删除操作；

1. public ListNode removeNthFromEnd(ListNode head, int n) {
2.         //新建一个虚拟头节点指向head
3.         ListNode dummyNode = new ListNode(0);
4.         dummyNode.next = head;
5.         //快慢指针指向虚拟头节点
6.         ListNode fastIndex = dummyNode;
7.         ListNode slowIndex = dummyNode;
9.         // 只要快慢指针相差 n 个结点即可
10.         for (int i = 0; i <= n; i++) {
11.             fastIndex = fastIndex.next;
12.         }
13.         while (fastIndex != null) {
14.             fastIndex = fastIndex.next;
15.             slowIndex = slowIndex.next;
16.         }
18.         // 此时 slowIndex 的位置就是待删除元素的前一个位置。
19.         // 具体情况可自己画一个链表长度为 3 的图来模拟代码来理解
20.         // 检查 slowIndex.next 是否为 null，以避免空指针异常
21.         if (slowIndex.next != null) {
22.             slowIndex.next = slowIndex.next.next;
23.         }
24.         return dummyNode.next;
25.     }

复制代码

3.第二种方法就是定义两个指针分别开始遍历两个链表，遍历完本链表就去遍历另外一条链表，如果遍历期间有相同的指针就是入口了。
这个原因是假设两个链表相交，那么他们的相同部分是c，不同部分分别是a,b,那么按照上述遍历，将会走同样长的路程就能得到入口点了；

1. (版本一)先行移动长链表实现同步移动
2. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         ListNode curA = headA;
4.         ListNode curB = headB;
5.         int lenA = 0, lenB = 0;
6.         while (curA != null) { // 求链表A的长度
7.             lenA++;
8.             curA = curA.next;
9.         }
10.         while (curB != null) { // 求链表B的长度
11.             lenB++;
12.             curB = curB.next;
13.         }
14.         curA = headA;
15.         curB = headB;
16.         // 让curA为最长链表的头，lenA为其长度
17.         if (lenB > lenA) {
18.             //1. swap (lenA, lenB);
19.             int tmpLen = lenA;
20.             lenA = lenB;
21.             lenB = tmpLen;
22.             //2. swap (curA, curB);
23.             ListNode tmpNode = curA;
24.             curA = curB;
25.             curB = tmpNode;
26.         }
27.         // 求长度差
28.         int gap = lenA - lenB;
29.         // 让curA和curB在同一起点上（末尾位置对齐）
30.         while (gap-- > 0) {
31.             curA = curA.next;
32.         }
33.         // 遍历curA 和 curB，遇到相同则直接返回
34.         while (curA != null) {
35.             if (curA == curB) {
36.                 return curA;
37.             }
38.             curA = curA.next;
39.             curB = curB.next;
40.         }
41.         return null;
42.     }
44. }

复制代码

142.环形链表II
算是链表比较有难度的题目，需要多花点时间理解 确定环和找环入口，建议先看视频。
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.环形链表II.html
题目感想：
1.首先我们要确定是否有环，可以定义两个快慢指针，快指针一下走两个，慢指针一下走一个，如果有环的话他们一定会相交，没有环的就会遍历到链表末尾；
2.有环就需要找到环的入口，这个推到过程可以去看上面的链接里面，详细介绍了为什么会在慢指针走在环中的第一圈相遇，以及为什么定义两个指针，一个从相遇节点出发，一个从起始节点出发，每次走一格，最终相遇的地方是环的入口；

1. (版本二) 合并链表实现同步移动
2. public class Solution {
3.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
4.                 // p1 指向 A 链表头结点，p2 指向 B 链表头结点
5.                 ListNode p1 = headA, p2 = headB;
6.                 while (p1 != p2) {
7.                         // p1 走一步，如果走到 A 链表末尾，转到 B 链表
8.                         if (p1 == null) p1 = headB;
9.                         else            p1 = p1.next;
10.                         // p2 走一步，如果走到 B 链表末尾，转到 A 链表
11.                         if (p2 == null) p2 = headA;
12.                         else            p2 = p2.next;
13.                 }
14.                 return p1;
15.     }
16. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！