检查子树 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。

如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。

示例1:

 输入：t1 = [1, 2, 3], t2 = [2]
 输出：true
示例2:

 输入：t1 = [1, null, 2, 4], t2 = [3, 2]
 输出：false
提示：

树的节点数目范围为[0, 20000]。
通过次数9,866提交次数13,693

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/check-subtree-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

检查当前节点是不是相等，如果相等分别检查两个树的左子树和右子树，如果不等，则分别检查大树的左子树和小树的根，大树的右子树和小树的根

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 a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean checkSubTree(TreeNode t1, TreeNode t2) {
        return t1 == t2 || healper(t1.left, t2) || healper(t1.right, t2);
    }
    public boolean healper(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null && t2 != null) return false;
        if (t1 != null && t2 == null) return true;
        if (t1.val == t2.val) {
            return healper(t1.left, t2.left) && healper(t1.right, t2.right);
        } else {
            return healper(t1.left, t2) || healper(t1.right, t2);
        }
    }
}

展开全文 >>

首个共同祖先 

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
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

    3
   / \
  5   1
 / \ / \
6  2 0  8
  / \
 7   4
示例 1:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-common-ancestor-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<TreeNode> list;
    List<TreeNode> path1;
    List<TreeNode> path2;

    boolean flag = false;

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)return root;
        if (p == null) return q;
        if (q == null) return p;
        list = new ArrayList<>();
        deep(root, p, q);

        TreeNode res = null;
        for (int i = 0; i < path1.size() && i < path2.size(); i++) {
            if (path1.get(i) == path2.get(i)) res = path1.get(i);
        }
        return res;
    }
    public void deep(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return;
        list.add(root);
        if (root == p || root == q) {
            if (!flag) {
                path1 = new ArrayList<>(list);
            } else {
                path2 = new ArrayList<>(list);
                return;
            }
            flag = true;
        }
        deep(root.left, p, q);
        deep(root.right, p, q);
        list.remove(list.size() - 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
class Solution {

    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
}

存储父节点

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
class Solution {
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}
1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/first-common-ancestor-lcci/solution/shou-ge-gong-tong-zu-xian-by-leetcode-so-c2sl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

最后一块石头的重量 

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
有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

示例：

输入：[2,7,4,1,8,1]
输出：1
解释：
先选出 7 和 8，得到 1，所以数组转换为 [2,4,1,1,1]，
再选出 2 和 4，得到 2，所以数组转换为 [2,1,1,1]，
接着是 2 和 1，得到 1，所以数组转换为 [1,1,1]，
最后选出 1 和 1，得到 0，最终数组转换为 [1]，这就是最后剩下那块石头的重量。

提示：

1 <= stones.length <= 30
1 <= stones[i] <= 1000
通过次数28,192提交次数44,981

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-stone-weight
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public int lastStoneWeight(int[] stones) {
               if (stones.length < 2) return stones[0];
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });

        for (int i = 0; i < stones.length; i++) {
            queue.offer(stones[i]);
        }

        while (!queue.isEmpty() && queue.size() > 1) {
            int max = queue.poll();
            if (!queue.isEmpty()) {
                int secondMax = queue.poll();
                if (max != secondMax) {
                    max -= secondMax;
                } else {
                    continue;
                }
            }
            if (max != 0) queue.offer(max);
        }

        if (!queue.isEmpty()) {
            return queue.poll();
        } else {
            return 0;
        }
    }
}

官方题解最大堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>((a, b) -> b - a);
        for (int stone : stones) {
            pq.offer(stone);
        }

        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            if (a > b) {
                pq.offer(a - b);
            }
        }
        return pq.isEmpty() ? 0 : pq.poll();
    }
}

参考文献

作者：LeetCode-Solution力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/last-stone-weight/solution/zui-hou-yi-kuai-shi-tou-de-zhong-liang-b-xgsx/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

后继者 

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
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2
示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null
通过次数11,733提交次数19,955

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/successor-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null || p == null) return null;
        boolean flag = false;
        Deque<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || root != null) {

            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (flag) return root;
            if (root == p) {
                flag = true;
            }

            root = root.right;

        }
        return null;
    }
}

展开全文 >>

最接近的三数之和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4
通过次数175,828提交次数383,553

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先排序

然后从开始固定一个数字，对于另外的两个数字从第一个数字之后使用双指针，一个在第一个数字之后，一个在数组的最后。如果三个数的和大于target,右指针right–，如果和小于target，左指针left++，同时记录每个与target差值最小的sum，返回

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
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);

        int minSum = Integer.MAX_VALUE;
        int minDiff = Integer.MAX_VALUE;

        int left = 0, right = nums.length - 1;
        for (int i = 0; i < nums.length; i++) {
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                int diff = Math.abs(sum - target);
                if (diff < minDiff) {
                    minDiff = diff;
                    minSum = sum;
                }

                if (target < sum) {
                    right--;
                } else if (target > sum) {
                    left++;
                } else {
                    return sum;
                }

            }

        }

        return minSum;
    }
}

展开全文 >>

特定深度节点链表 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。

示例：

输入：[1,2,3,4,5,null,7,8]

        1
       /  \ 
      2    3
     / \    \ 
    4   5    7
   /
  8

输出：[[1],[2,3],[4,5,7],[8]]
通过次数13,806提交次数17,179

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/list-of-depth-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
53
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode[] listOfDepth(TreeNode tree) {
        if (tree == null) return new ListNode[]{};

        Queue<TreeNode> queue = new LinkedList<>();

        queue.offer(tree);

        List<ListNode> list = new ArrayList<>();

        while (!queue.isEmpty()) {
            int size = queue.size();

            TreeNode root = queue.poll();
            ListNode node = new ListNode(root.val);
            list.add(node);

            if (root.left != null) queue.offer(root.left);
            if (root.right != null) queue.offer(root.right);
            for (int i = 1; i < size; i++) {
                root = queue.poll();
                node.next = new ListNode(root.val);
                node = node.next;
                if (root.left != null) queue.offer(root.left);
                if (root.right != null) queue.offer(root.right);
            }
        }

        ListNode[] res = new ListNode[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}

展开全文 >>

按要求补齐数组

330. 按要求补齐数组

难度：困难

给定一个已排序的正整数数组 nums和一个正整数 *n，从 [1, n] 区间内选取任意个数字补充到 *nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。

示例 1:

1
2
3
4
5
6
7
输入: nums = [1,3], n = 6
输出: 1 
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。

示例 2:

1
2
3
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。

示例 3:

1
2
输入: nums = [1,2,2], n = 5
输出: 0

贪心

对于正整数 x，如果区间 [1,x-1] 内的所有数字都已经被覆盖，且 x 在数组中，则区间 [1,2x-1] 内的所有数字也都被覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minPatches(int[] nums, int n) {
        int addNum = 0;
        long x = 1;
        int length = nums.length, index = 0;
        while (x <= n) {
            if (index < length && nums[index] <= x) {
                x += nums[index];
                index++;
            } else {
                x *= 2;
                addNum++;
            }
        }
        return addNum;
    }
}

参考文献

按要求补齐数组
力扣官方题解

1
2
3
4
5
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/patching-array/solution/an-yao-qiu-bu-qi-shu-zu-by-leetcode-solu-klp1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

节点间通路 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例1:
 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 输出：true

示例2:
 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 输出 true
提示：

节点数量n在[0, 1e5]范围内。
节点编号大于等于 0 小于 n。
图中可能存在自环和平行边。
通过次数9,562提交次数18,034

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        Map<Integer, Set<Integer>> neiTable = new HashMap<>();

        for (int i = 0; i < graph.length; i++) {
            if (graph[i][0] == graph[i][1]) continue;
            neiTable.computeIfAbsent(graph[i][0], k -> new HashSet<>()).add(graph[i][1]);
        }

        return dfs(neiTable, start, target);
    }
    public boolean dfs(Map<Integer, Set<Integer>> neiTable, int start, int target) {
        if (start == target) return true;
        for (Integer nei : neiTable.getOrDefault(start, new HashSet<>())) {
            if (dfs(neiTable, nei, target)) return true;
        }
        return false;
    }
}

参考文献

深度优先搜索作者：王小强

展开全文 >>

堆盘子 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
堆盘子。设想有一堆盘子，堆太高可能会倒下来。因此，在现实生活中，盘子堆到一定高度时，我们就会另外堆一堆盘子。请实现数据结构SetOfStacks，模拟这种行为。SetOfStacks应该由多个栈组成，并且在前一个栈填满时新建一个栈。此外，SetOfStacks.push()和SetOfStacks.pop()应该与普通栈的操作方法相同（也就是说，pop()返回的值，应该跟只有一个栈时的情况一样）。 进阶：实现一个popAt(int index)方法，根据指定的子栈，执行pop操作。

当某个栈为空时，应当删除该栈。当栈中没有元素或不存在该栈时，pop，popAt 应返回 -1.

示例1:

 输入：
["StackOfPlates", "push", "push", "popAt", "pop", "pop"]
[[1], [1], [2], [1], [], []]
 输出：
[null, null, null, 2, 1, -1]
示例2:

 输入：
["StackOfPlates", "push", "push", "push", "popAt", "popAt", "popAt"]
[[2], [1], [2], [3], [0], [0], [0]]
 输出：
[null, null, null, null, 2, 1, 3]
通过次数3,995提交次数10,710

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/stack-of-plates-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
class StackOfPlates {
    private static class MStack {
        int cap = 0;
        List<Integer> stack = null;

        public MStack(int cap) {
            this.cap = cap;
            stack = new ArrayList<>();
        }

        public int pop() {
            if (!stack.isEmpty()) {
                int index = stack.size() - 1;
                int res = stack.get(index);
                stack.remove(index);
                return res;
            } else {
                return -1;
            }
        }

        public boolean push(Integer val) {
            if (stack.size() < cap) {
                stack.add(val);
                return true;
            } else {
                return false;
            }
        }

        public int getSize() {
            return stack.size();
        }

    }
    int cap = 0;
    List<MStack> stackList = null;
    public StackOfPlates(int cap) {
        this.cap = cap;
        this.stackList = new ArrayList<>();
    }
    
    public void push(int val) {
        if (stackList.isEmpty()) {
            MStack s = new MStack(cap);
            s.push(val);
            stackList.add(s);
        } else {
            boolean isSucc = stackList.get(stackList.size() - 1).push(val);
            if (!isSucc) {
                MStack s = new MStack(cap);
                s.push(val);
                stackList.add(s);
            }
        }
    }
    
    public int pop() {
        int res = -1;
        if (!stackList.isEmpty()) {
            int index = stackList.size() - 1;
            MStack s = stackList.get(index);
            res = s.pop();
            if (s.getSize() == 0) {
                stackList.remove(index);
            }
            return res;
        } else {
            return -1;
        }
    }
    
    public int popAt(int index) {
        int res = -1;
        if (index < stackList.size()) {
            MStack s = stackList.get(index);
            res = s.pop();
            if (s.getSize() == 0) {
                stackList.remove(index);
            }
        }
        return res;
    }
}

/**
 * Your StackOfPlates object will be instantiated and called as such:
 * StackOfPlates obj = new StackOfPlates(cap);
 * obj.push(val);
 * int param_2 = obj.pop();
 * int param_3 = obj.popAt(index);
 */

展开全文 >>

环路检测

环形链表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
给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

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

示例 1：

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

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

输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：

你是否可以不用额外空间解决此题？
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三个指针，第一个指针每次走两步，第二个指针每次走一步，当两个指针相遇的时候，从头节点出发一个每次走一步的节点，慢指针和最后出发的指针相遇的时候即是入口节点

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
/**
 * Definition for singly-linked list.
                                                   
 */
public class Solution {
    //三个指针，第一个指针每次走两步，第二个指针每次走一步，当两个指针相遇的时候，
    // 从头节点出发一个每次走一步的节点，慢指针和最后出发的指针相遇的时候即是入口节点
    public ListNode detectCycle(ListNode head) {
        if (head == null) return head;

        ListNode fast = head;
        ListNode slow = head;
        ListNode third = null;

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

            if (fast != null) {
                fast = fast.next;
                if (fast != null) {
                    if (fast.equals(slow)) {
                        third = head;

                        while (!slow.equals(third)) {
                            slow = slow.next;
                            third = third.next;
                        }
                        
                        return third;
                    }
                }
            }
        }
        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
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;              //快指针每次走两步，慢指针每次走一步
        while (fast != null) {
            slow = slow.next;                           //走一步
            if (fast.next != null) {
                fast = fast.next.next;                  //走两步
            } else {
                return null;
            }
            if (fast == slow) {                         //快指针和慢指针相遇时
                ListNode ptr = head;                    //从头指针出发一个指针，直到与慢指针相遇，这时候两个指针的相遇点就是入环点
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

参考文献

作者：LeetCode-Solution 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走