hxy的博客

Mia san Mia!

0%

链表刷题

发表于 更新于 分类于 Valine：

按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是链表

专题部分

链表

2. 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

img

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

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

示例 3：

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

提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

主要是要注意进位和只有一个链表还有一位的情况

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} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let dummy = new ListNode();
    let pre  = dummy;
    let flag = 0;
    while (l1 || l2 || flag) {
        let x1 = l1 !== null ? l1.val: 0;  
        let x2 = l2 !== null ? l2.val: 0;  
        flag = x1 + x2 + flag;
        let node = new ListNode(flag % 10);
        pre.next = node;
        pre = pre.next;
        flag = Math.floor(flag / 10);
        l1 && (l1 = l1.next);
        l2 && (l2 = l2.next);
    }
    return dummy.next;
};

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

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

进阶：你能尝试使用一趟扫描实现吗？

示例 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) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 * 双指针
 */
var removeNthFromEnd = function(head, n) {
    let dummy = new ListNode(null);
    dummy.next = head;
    let slow = dummy;
    let fast = dummy;
    for(let i = 0; i <= n; i ++) {
        fast = fast.next;
    }
    while(fast !== null) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return dummy.next;
};

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

1
2
输入：lists = []
输出：[]

示例 3：

1
2
输入：lists = [[]]
输出：[]

提示：

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] 按 升序 排列
  • lists[i].length 的总和不超过 10^4

先写出归并2个有序链表的函数，然后归并排序

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
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
 * 
 * @param lists ListNode类一维数组 
 * @return ListNode类
 */
function mergeKLists( lists ) {
    // write code here
    const len = lists.length;
    if (len === 0) return null;
    if (len === 1) return lists[0];
    return mergeTwoLists(mergeKLists(lists.slice(0, len >> 1)), mergeKLists(lists.slice(len >> 1)));
}
function mergeTwoLists( l1 ,  l2 ) {
    // write code here
    if (!l1) return l2;
    if (!l2) return l1;
    // 头指针
    let dummy = new ListNode(0);
    // 当前指针
    let cur = dummy;
    // 两个数组均有数
    while (l1 !== null && l2 !== null) {
        if (l1.val <= l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        // 当前指针前进
        cur = cur.next;
    }
    // 将未遍历完的赋值
    cur.next = l1 ? l1 : l2;
    return dummy.next;
}

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

  • 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
  • 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

img

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

示例 2：

img

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

示例 3：

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

示例 4：

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

提示：

  • 列表中节点的数量在范围 sz 内
  • 1 <= sz <= 5000
  • 0 <= Node.val <= 1000
  • 1 <= k <= 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
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
    if (head === null) return head;
    // 区间 [a, b) 包含 k 个待反转元素
    let a = head, b = head;
    for (let i = 0; i < k; i++) {
        // 不足 k 个，不需要反转，base case
        if (b === null) return head;
        b = b.next;
    }
    // 反转前 k 个元素
    let newHead = reverse(a, b);
    // 递归反转后续链表并连接起来
    a.next = reverseKGroup(b, k);
    return newHead;
};

function reverse (head, tail) {
    let pre = null, cur = head, next;
    while (cur !== tail) {
        next = cur.next;
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = next;
    }
    // 返回反转后的头结点
    return pre;
}

先统计数量，再K个一组翻转

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
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param k int整型 
  * @return ListNode类
  */
function reverseKGroup( head ,  k ) {
    // write code here
    if (!head || !head.next || k < 2) return head;
    let dummy = new ListNode(0);
    dummy.next = head;
    let pre = dummy;
    let cur = head;
    let len = 0;
    while (head) {
        len++;
        head = head.next;
    }
    for (let i = 0; i < Math.floor(len / k); i++) {
        for (let j = 1; j < k; j++) {
            // 翻转之后头结点会变成尾节点，此时指向头结点的下一个节点会成为新的头结点。
            let next = cur.next;
            // 每次翻转一个节点，尾节点指向第三个节点。
            cur.next = next.next;
            // 翻转
            next.next = pre.next;
            // pre.next指向翻转后的头结点
            pre.next = next;
        }
        // 每K个节点的哑节点
        pre = cur;
        // 每K个节点的首节点
        cur = cur.next;
    }
    return dummy.next;
}

链表内指定空间翻转

题目描述

将一个链表m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。
例如：
给出的链表为1→2→3→4→5→NULL, m=2,n=4,
返回 1→4→3→2→5→NULL.
注意：
给出的 m,n 满足以下条件：
1≤m≤n≤链表长度

示例1

输入

1
{1,2,3,4,5},2,4

返回值

1
{1,4,3,2,5}

找到头部和尾部，进行翻转

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
/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
  */
function reverseBetween(head,  m,  n) {
    // 哑节点
    let dummy = new ListNode(0);
    dummy.next = head;
    let pre = dummy, cur = head;
    // 找到第一个需要翻转的节点
    for (let i = 0; i < m; i++) {
        pre = pre.next;
        cur = cur.next;
    }
    for (let j = 0; j < n - m; j++) {
        // 跳过一个节点，记为next
        let next = cur.next;
        cur.next = next.next;
        // 将该节点插入需要反转的头部
        next.next = pre.next;
        pre.next = next;
    }
    let dummy = new ListNode(0);
    dummy.next = head;
    let pre = dummy;
    let cur = head;
    for (let i = 0; i < m - 1; i++) {
        pre = pre.next;
        cur = cur.next;
    }
    for (let j = 0; j < n - m; j++) {
        let temp = cur.next;
        cur.next = temp.next;
        temp.next = pre.next;
        pre.next = temp;
    }
    return dummy.next;
}
module.exports = {
    reverseBetween : reverseBetween
};

141. 环形链表

给定一个链表，判断链表中是否有环。

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

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

进阶：

你能用 *O(1)*（即，常量）内存解决此问题吗？

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

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let fast = head, slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast === slow) return true;
    }
    return false;
};

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

  • 你是否可以使用 O(1) 空间解决此题？

示例 1：

img

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

示例 2：

img

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

示例 3：

img

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

提示：

  • 链表中节点的数目范围在范围 [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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    // 哈希表
    const visited = new Set();
    while (head !== null) {
        if (visited.has(head)) {
            return head;
        }
        visited.add(head);
        head = head.next;
    }
    return null;
};

快慢指针

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) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let slow = head, fast = head;
    // 判断是否存在环路
    do {
        if (!fast || !fast.next) return null;
        fast = fast.next.next;
        slow = slow.next;
    } while (fast !== slow);
    // 如果存在，查找环路节点
    fast = head;
    while (fast !== slow){
        slow = slow.next;
        fast = fast.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
/**
 * 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 === null || head.next === null) return null;
    
    // 获取相遇节点
    function getIntersect(head) {
        let fast = head, slow = head;
        while(fast !== null && fast.next !== null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast === slow) {
                return slow;
            }
        }
        return null;
    }
    
    const intersect = getIntersect(head);
    if (intersect === null) {
        return null;
    }
    let p1 = head, p2 = intersect;
    while(p1 !== p2) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
};

或者直接一次判断是否有环以及环在哪里

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head, slow = head;
    while (fast !== null && fast.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) {
            let num = 0;
            let cur = head;
            while (cur != fast) {
                cur = cur.next;
                fast = fast.next;
                num++;
            }
            return cur;
        }
    }
    return null;
};

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

img

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

img

1
2
3
4
5
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

img

1
2
3
4
5
输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

img

1
2
3
4
5
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
0 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶：你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案？

使用双指针完成设计

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}
 */
var getIntersectionNode = function(headA, headB) {
    let pointA = headA, pointB = headB;
    while (pointA !== pointB) {
        pointA = pointA ? pointA.next : headB;
        pointB = pointB ? pointB.next : headA;
    }
    return pointA;
};

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

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

示例 2：

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

示例 3：

1
2
输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= k <= 50

直接使用哑节点了，很方便

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
/**
 * 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} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
    // 哑节点
    let dummy = new ListNode(0);
    dummy.next = head;
    let cur = dummy;
    while (cur.next !== null) {
        if (cur.next.val === val) {
            cur.next = cur.next.next;
        } else if (cur.next !== null) {
            cur = cur.next;
        }
    }
    return dummy.next;
};

234. 回文链表

请判断一个链表是否为回文链表。

示例 1:

1
2
输入: 1->2
输出: false

示例 2:

1
2
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    let left = head;
    return traverse(head);

    function traverse(right) {
        if (right === null) return true;
        let res = traverse(right.next);
        // 后序遍历代码
        res = res && (right.val === left.val);
        left = left.next;
        return res;
    }
}

快慢指针找到终点翻转后半部分

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function(head) {
    // 先通过「双指针技巧」中的快慢指针来找到链表的中点
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow 指针现在指向链表中点

    // 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
    if (fast !== null) slow = slow.next;

    // 从slow开始反转后面的链表，现在就可以开始比较回文串了
    let left = head;
    let right = reverse(slow);

    while (right !== null) {
        if (left.val !== right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    return true;

    function reverse(head) {
        let pre = null, cur = head;
        while (cur !== null) {
            let next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

大佬写的代码很规范，抄了过来，本质上是一样的

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
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 * 常数空间
 */
var isPalindrome = function(head) {
    if (!head) return true;

    // 找到前半部分链表的尾节点并反转后半部分链表
    const firstHalfEnd = endOfFirstHalf(head);
    const secondHalfStart = reverseList(firstHalfEnd.next);

    // 判断是否回文
    let p1 = head, p2 = secondHalfStart;
    let result = true;
    while (result && p2 != null) {
        if (p1.val != p2.val) result = false;
        p1 = p1.next;
        p2 = p2.next;
    }

    // 还原链表并返回结果
    firstHalfEnd.next = reverseList(secondHalfStart);
    return result;
};

const endOfFirstHalf = (head) => {
    let fast = head, slow = head;
    while (fast.next !== null && fast.next.next !== null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

const reverseList = (head) => {
    let prev = null, curr = head;
    while (curr !== null) {
        let nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

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

示例 2：

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

示例 3：

1
2
输入：nums = [1,1]
输出：1

示例 4：

1
2
输入：nums = [1,1,2]
输出：1

提示：

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • nums 中 只有一个整数 出现 两次或多次 ，其余整数均只出现 一次

进阶：

  • 如何证明 nums 中至少存在一个重复的数字?
  • 你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

使用环形链表II的方法解题（142.环形链表II），使用 142 题的思想来解决此题的关键是要理解如何将输入的数组看作为链表。
首先明确前提，整数的数组 nums 中的数字范围是 [1,n]。考虑一下两种情况：

1.如果数组中没有重复的数，以数组 [1,3,4,2]为例，我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)f(n)，
其映射关系 n->f(n)为：
0->1
1->3
2->4
3->2
我们从下标为 0 出发，根据 f(n)f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。这样可以产生一个类似链表一样的序列。
0->1->3->2->4->null

2.如果数组中有重复的数，以数组 [1,3,4,2,2] 为例,我们将数组下标 n 和数 nums[n] 建立一个映射关系 f(n)f(n)，
其映射关系 n->f(n) 为：
0->1
1->3
2->4
3->2
4->2
同样的，我们从下标为 0 出发，根据 f(n)f(n) 计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推产生一个类似链表一样的序列。
0->1->3->2->4->2->4->2->……
这里 2->4 是一个循环，那么这个链表可以抽象为下图：

img

从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了，

综上
1.数组中有一个重复的整数 <==> 链表中存在环
2.找到数组中的重复整数 <==> 找到链表的环入口

至此，问题转换为 142 题。那么针对此题，快、慢指针该如何走呢。根据上述数组转链表的映射关系，可推出
142 题中慢指针走一步 slow = slow.next ==> 本题 slow = nums[slow]
142 题中快指针走两步 fast = fast.next.next ==> 本题 fast = nums[nums[fast]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;
    slow = nums[slow];
    fast = nums[nums[fast]];
    while(slow !== fast){
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    let pre1 = 0;
    let pre2 = slow;
    while(pre1 !== pre2){
        pre1 = nums[pre1];
        pre2 = nums[pre2];
    }
    return pre1;
}

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1:

1
2
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

1
2
输入: 2->1->3->5->6->4->7->NULL 
输出: 2->3->6->7->1->5->4->NULL

说明:

  • 应当保持奇数节点和偶数节点的相对顺序。
  • 链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。
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} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    if (head === null) return head;
    let evenHead = head.next;
    // 奇指针，偶指针
    let odd = head, even = evenHead;
    // 迭代
    while (even !== null && even.next !== null) {
        // 奇指针下个节点指向当前偶节点的下一个指针
        odd.next = even.next;
        // 奇指针前移
        odd = odd.next;
        // 偶指针下个节点指向当前奇节点的下一个指针
        even.next = odd.next;
        // 偶指针前移
        even = even.next;
    }
    // 奇指针末尾节点指向偶指针第一个节点
    odd.next = evenHead;
    return head;
};
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道