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

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

题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

解题思路

1. 双指针法

双指针的经典应用，如果要删除倒数第 n 个节点，让 fast 移动 n 步，然后让 fast 和 slow 同时移动，直到 fast 指向链表末尾。删掉 slow 所指向的节点就可以了。

1. 定义 fast 指针和 slow 指针，初始值为虚拟头结点
2. fast 首先走 n + 1 步 ，为什么是 n+1 呢，因为只有这样同时移动的时候 slow 才能指向删除节点的上一个节点（方便做删除操作）
3. fast 和 slow 同时移动，之道 fast 指向末尾
4. 删除 slow 指向的下一个节点

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let dummyHead = new ListNode(0); // 设置一个虚拟头结点
  dummyHead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
  let slow = dummyHead; // 慢指针
  let fast = dummyHead; // 快指针

  // 让快指针先走n步
  while (n--) {
    fast = fast.next;
  }

  fast = fast.next; // fast再提前走一步，因为需要让slow指向删除节点的上一个节点

  // 让fast和slow同时移动，直到fast指向链表末尾
  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  // 删除节点
  slow.next = slow.next.next;
  return dummyHead.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

24. 两两交换链表中的节点[TODO]

题目链接：https://leetcode-cn.com/problems/swap-nodes-in-pairs/

解题思路

1. 迭代法

当前节点(cur)的下一个节点(node1)与下下一个节点(node2)交换。
a. cur 的 next 为 node2。
b. node2 的 next 为 node1。
c. node1 的 next 为 node2 的下一个节点。
将 cur 跳两步，即指向 node1。
终结条件为 cur 没有下一个节点或下下个节点。
由于需要从链表头节点开始交换，所以我们需要在链表头节点添加一个节点 dummy。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  let dummyHead = new ListNode(0); // 设置一个虚拟头结点
  dummyHead.next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
  let cur = dummyHead;
  while (cur.next != null && cur.next.next != null) {
    let tmp = cur.next; // 记录临时节点
    tmp1 = cur.next.next.next; // 记录临时节点

    cur.next = cur.next.next; // 步骤一
    cur.next.next = tmp; // 步骤二
    cur.next.next.next = tmp1; // 步骤三

    cur = cur.next.next; // cur移动两位，准备下一轮交换
  }
  return dummyHead.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.

题目要求不能改变节点里面的值。

1）首先先定义一个不动的首节点firstNode，后面节点移来移去时才不会受影响
2）以[1, 2, 3, 4]为例，一开始要交换的是[1, 2]，因此需要先储存[3, 4]，稍后再处理（下图 1）
3）存储后将list要处理的部分[1, 2]跟不处理的部分[3, 4]切开（下图 2），切开的同时让[2]的 next 指向[1]
4）将前一个节点prev的next指向[2]，因为[2]的 next 已经指向[1]，因此这边已经完成[1, 2]->[2, 1]的步骤
5）接下来把之前存储的[3, 4]接到[1]后面，就可以继续处理[3, 4]


代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  let firstNode = new ListNode(0); // 设置一个虚拟头结点

  firstNode.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作

  let cur = head;
  let prev = firstNode;

  // 图1的部分, 目前除了的结点cur，前一个节点prev

  let nextKeep; // 预备用于存储后面未处理的节点

  while (cur != null && cur.next != null) {
    // 图1，将后面的结点[3,4]存储起来
    nextKeep = cur.next.next; // 记录临时节点
    // 图2，将[1,2]与[3,4]断开，这时候[2]的next已经变成[1]
    cur.next.next = cur;
    // 图3，将prev的next指向[2]，注意这时候[2]的next已经指向[1]
    // 整理一下其实如图4
    prev.next = cur.next;

    // 图5,将[3,4]接回[1]
    cur.next = nextKeep;

    // 处理下一组
    prev = cur;
    cur = cur.next;
  }
  return firstNode.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

142.环形链表 II[TODO]

题目链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/

解题思路

1. 快慢指针

1. 声明两个指针快指针fast、慢指针slow
2. 判断链表是否有环：fast、slow从头部出发，fast走两步，slow走一步，如果可以相遇，则环存在
3. 从环内某个节点开始计数，再回到此节点时得到链表环的长度length
4. fast、slow回到head节点，让fast先走length步，当slow和fast相遇时即为链表环的起点

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  if (!head || !head.next) {
    return null;
  }

  let slow = head.next;
  let fast = head.next.next;

  // 1. 判断是否有环
  while (fast !== slow) {
    if (fast === null || fast.next === null) {
      return null;
    }

    slow = slow.next;
    fast = fast.next.next;
  }

  // 2. 获取环的长度
  let temp = fast;
  let length = 1;
  slow = slow.next;

  while (temp !== slow) {
    slow = slow.next;
    length++;
  }

  // 3. 找公共节点
  fast = slow = head;
  while (length--) {
    fast = fast.next;
  }
  while (fast !== slow) {
    fast = fast.next;
    slow = slow.next;
  }

  return fast;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52