参阅基础

简介

双指针，指的是在遍历对象的过程中，不使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组（或链表）有序这一特征，从而在某些情况下能够简化一些运算。

对于单链来说，大部份技巧都属于快慢指针。

此外，链表算法题还有个很常见的「虚拟头结点」技巧。就是在实际的链表头前放一个 dummy 节点，作为占位符，可以避免处理空指针的情况，降低代码的复杂性。

相关习题

LeedCode 21.合并两个有序链表

题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

来源：https://leetcode.cn/problems/merge-two-sorted-lists/

示例 1：

img

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

1
2
输入：l1 = [], l2 = []
输出：[]

示例 3：

1
2
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

我的题解

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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function(list1, list2) {
  let listNodeHead = new ListNode(0),
  cur = listNodeHead,p1 = list1,p2 = list2

  while(p1 != null && p2 != null){
      if(p1.val >= p2.val){
          cur.next = p2
          p2 = p2.next
      }else{
          cur.next = p1
          p1 = p1.next
      }
      cur = cur.next
  }

  cur.next = p1 ? p1 : p2;

  return listNodeHead.next
};

LeedCode 86.分隔链表

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

来源：https://leetcode.cn/problems/partition-list/

示例 1：

img

1
2
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

示例 2：

1
2
输入：head = [2,1], x = 2
输出：[1,2]

提示：

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200

我的题解

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
/**
 * 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} x
 * @return {ListNode}
 */
var partition = function(head, x) {
    // 分别用两条链表来进行获取内容，最后进行简单拼接即可
    let dummy1 = new ListNode(-1), p1 = dummy1
    let dummy2 = new ListNode(-1), p2 = dummy2
    let p = head
    // 通过p指针来比较每个节点应该放置在哪一条链子上
    while(p != null) {
        // >= 需要考虑相等的结果，相等的时候也放在第二条链子 p2上面
        if(p.val >= x) {
            p2.next = p
            p2 = p2.next
        }else {
            p1.next = p
            p1 = p1.next
        }
        // 要保持原链表，所以每个节点遍历比较完以后应该断开
        let temp = p.next
        p.next = null
        p = temp
    }
    p1.next = dummy2.next
    return dummy1.next
};

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

题目

难度中等2187收藏分享切换为英文接收动态反馈

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

来源：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

示例 1：

img

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

我的题解

核心技巧：快慢指针

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
/**
 * 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 res = new ListNode(0,head),fast = slow = res

    while(n--){
       fast = fast.next
    }

    while(fast.next != null){
       fast = fast.next
       slow = slow.next
    }

    slow.next = slow.next.next

    return res.next
};

LeedCode 141.环形链表

注意：Leetcode的运行机制（根据输入执行实例构建题目的数据结构）

题目

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

来源：https://leetcode.cn/problems/linked-list-cycle/

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

我的题解

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */

var hasCycle = function(head) {
    //设置快慢指针
    let slow = head;
    let fast = head;
    //如果没有环，则快指针会抵达终点，否则继续移动双指针
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        //快慢指针相遇，说明含有环
        if (slow == fast) {
            return true;
        }
    }

    return false;
};