Leetcode链表刷题思路汇总

链表

链表相关的题，最快的入门方法就是做题的时候画图。标注A的next节点是哪里，单链表的遍历只能是单向的，从头结点到尾结点。

例如：给你一个链表的head头，让你返回最后元素的值
if (head == null) {
	return -1;
}
while (head.next != null) {
	head = head.next;
}
return head.val;
1
2
3
4
5
6
7
8

最近花了大概一个月的时间，将链表的专题刷完了，记录总结一下，题怎么刷比较容易理解，常规套路还有一些题的题解。

一些常规套路

1、对于大部分链表的题，我们都需要一个哑结点，就是在头结点之前再创建一个节点并将哑结点的next指向head，这样处理会帮助我们解决边界问题。

2、链表题基本都是对next指针的调整，而不是值本身。

3、对于删除来说就是找前驱，一般会用到快慢双指针。(例如第19题，删除倒数第n个节点)

4、一般来说我们要返回的和过程中处理的是两个引用，因为过程中处理的需要不断的cur = cur.next。而返回时要返回头结点。

5、对于改next指针的时候注意不要路径覆盖，否则会导致死循环。例如(Q24交换链表节点)

6、对于找链表中位数，就是快慢指针，快指针一次移动两次，慢指针一次移动一次。

7、关于环、快慢指针，当fast==slow时证明有环，此时head和slow边移动边比较，相等时就是入环的点。

算法

1、两数之和(2)

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

请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

链接：https://leetcode-cn.com/problems/add-two-numbers

思路：将两个链表当前节点值(当前链表为null，值就是0)相加并加上进位，进位初始化为0，然后创建新的链表对象，新的对象的val为结果%10;然后如果两个链表哪个不为null就往后遍历。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int add = 0;
        //  cur 作为不断变化的指针
        ListNode cur = new ListNode(0);
        //  res 指向cur后不再变化
        ListNode res = cur;
        while (l1!=null || l2!=null){
            int a1 = l1!=null?l1.val:0;
            int a2 = l2!=null?l2.val:0;
            int sum = a1+a2+add;
            add = sum / 10;
            // cur next开始存的是真正的结果
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1!=null){
                l1 = l1.next;
            }
            if (l2!=null){
                l2 = l2.next;
            }
        }
        if (add > 0){
            cur.next = new ListNode(add);
        }
        return res.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

2、删除倒数第n个链表

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

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

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

思路：哑结点，快慢指针，慢指针指向哑结点，快指针走n步后，快慢一起走。slow.next = slow.next.next移除。

public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        // 添加哑结点
        ListNode res = new ListNode(0,head);
        // slow 和 res指向同一个地址
        ListNode slow = res;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、合并两个升序链表(21)

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

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

思路：判断A>B就创建个新的往结果加，最后A，B哪个不为空再加到最后。

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 使用哑结点免去头结点判断代码
        ListNode cur = new ListNode(0);
        // res是真正从头到尾的链表，cur是控制当前节点动的。
        ListNode res = cur;
        while (l1!=null && l2!=null){
            if (l1.val<=l2.val){
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            }else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if (l1!=null){
            cur.next = l1;
        }
        if (l2!=null){
            cur.next = l2;
        }
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、合并K个升序链表(23)

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

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

输入：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
1
2
3
4
5
6
7
8
9
10

思路：归并排序

public ListNode mergeKLists(ListNode[] lists) {
        return mergeList(lists,0,lists.length-1);
    }

    public ListNode mergeList(ListNode[] lists,int head,int tail){
        if (head == tail){
            return lists[head];
        }
        if (head > tail){
            return null;
        }
        int mid = (head+tail)/2;
        return merge(mergeList(lists,head,mid),mergeList(lists,mid+1,tail));
    }

    private ListNode merge (ListNode l1,ListNode l2){
        ListNode res = new ListNode(-1);
        ListNode ans = res;
        while (l1!=null && l2!=null){
            if (l1.val <= l2.val){
                res.next = l1;
                l1 = l1.next;
            }else {
                res.next = l2;
                l2 = l2.next;
            }
            res = res.next;
        }
        if (l1!=null){
            res.next = l1;
        }
        if (l2!=null){
            res.next = l2;
        }
        return ans.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

5、两两交换链表中的节点(24)

题目：给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

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

思路：利用哑结点，设置next next.next 节点转换，循环就行了，注意的是cur一下跳两个节点

    public static ListNode swapPairs(ListNode head) {
        ListNode cur = new ListNode(-1);
        cur.next = head;
        ListNode res = cur;
        while (cur.next!=null && cur.next.next!=null){
            ListNode tmp1 = cur.next;
            ListNode tmp2 = cur.next.next;
            tmp1.next = tmp2.next;
            tmp2.next = tmp1;
            cur.next = tmp2;
            cur = cur.next.next;
        }
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6、K 个一组翻转链表(25)

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

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

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

进阶：

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

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

思路：每k个链表反转，最后拼到一起就行了

public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        int len = 0;
        List<ListNode> all = new ArrayList<>();
        ListNode cur = head;
        while (cur != null) {
            len++;
            if (len == k) {
                len = 0;
                ListNode next = cur.next;
                cur.next = null;
                all.add(head);
                head = next;
                cur = next;
            } else {
                cur = cur.next;
            }
        }
        return reverse(all, head);
    }

    public ListNode reverse(List<ListNode> heads, ListNode end) {
        ListNode res = new ListNode(-1);
        ListNode ans = res;
        for (ListNode head : heads) {
            ListNode pre = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            res.next = pre;
            while (res.next!=null){
                res = res.next;
            }
        }
        res.next = end;
        return ans.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
42
43

7、旋转链表(61)

题目：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

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

思路：将链表连成环，然后移动，然后再将环拆开，

public static ListNode rotateRight(ListNode head, int k) {
        // 只有头节点是null的时候需要特殊处理一下
        if (head == null) {
            return null;
        }
        ListNode low = head;
        ListNode fast = head;
        int len = 1;
        while (fast!=null){
            if (fast.next == null){
                // 到链表最后一个节点了，此时将链表连成一个环
                fast.next = head;
                break;
            }
            fast = fast.next;
            len++;
        }
        k = k%len;
        int loop = len-k;
        //  len-k代表的是移动方向几次low指向头结点，画图能看出来端倪
        while (loop > 0){
            low = low.next;
            fast = fast.next;
            loop--;
        }
        fast.next=null;
        return low;
    }
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

8、删除排序链表中的重复元素 II(82)

题目：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

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

思路：找当前的节点和后继节点比较，值一样，while判断后面还有没有一样的，一样的全去掉。如果当前和后继不一样就往后移动一位

public static ListNode deleteDuplicates(ListNode head) {
       ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur.next!=null && cur.next.next!=null){
            if (cur.next.val == cur.next.next.val){
                int x = cur.next.val;
                while (cur.next!=null && x == cur.next.val){
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return res.next;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

9、删除排序链表中的重复元素(83)

题目：存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

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

思路：下一个跟当前相同，就把下一个删了。

public static ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        ListNode res = cur;
        while (cur!=null && cur.next!=null){
            if (cur.val == cur.next.val){
                cur.next = cur.next.next;
            }else {
                cur = cur.next;
            }
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12

10、分隔链表(86)

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

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

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

思路：创建大小两个链表，遍历一遍将大小分开组装，然后大小链表拼起来就行了

public static ListNode partition(ListNode head, int x) {
        ListNode cur = head;
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        ListNode res = small;
        ListNode tmpBig = big;
        while (cur!=null){
            if (cur.val<x){
                small.next = new ListNode(cur.val);
                small = small.next;
            }else {
                big.next = new ListNode(cur.val);
                big = big.next;
            }
            cur = cur.next;
        }
        small.next = tmpBig.next;
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

11、反转链表 II(92)

题目：给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

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

思路：穿针引线把经过的节点放到最前面这样经过[left,right]部分就是反转的了，头插法。先找到pre

public static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode pre = res;
        int tmpLeft = left;
        while (left > 1) {
            left--;
            pre = pre.next;
        }
        ListNode cur = pre.next;
        int tmp = right - tmpLeft;
        ListNode cNext;
        while (tmp > 0) {
            tmp--;
            cNext = cur.next;
            cur.next = cNext.next;
            cNext.next = pre.next;
            pre.next = cNext;

        }
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

12、有序链表转换二叉搜索树(109)

题目：给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

给定的有序链表： [-10, -3, 0, 5, 9],

一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：

       0
      / \
    -3   9
   /   /
 -10  5
1
2
3
4
5

思路：这个就是前序遍历建树就行了。恢复成BST 不断的找中位数，因为链表是有序的，递归时每次把中间的数加为节点进行构造二叉树就可以了

public TreeNode sortedListToBST(ListNode head) {
        return createNode(head, null);
    }

    TreeNode createNode(ListNode head, ListNode tail) {
        // 当头==尾时，说明当前节点下面没有子树了。
        if (head == tail) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != tail && fast.next != tail) {
            fast = fast.next.next;
            slow = slow.next;
        }
        TreeNode root = new TreeNode(slow.val);
        root.left = createNode(head, slow);
        root.right = createNode(slow.next, tail);
        return root;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

13、复制带随机指针的链表(138)

题目：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
1
2

思路：先复制一份node，A-A’-B-B’-C-C’这样，然后每个节点的random再复制，副本的random等于原random的next；最后再将其拆开。

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        while (cur != null) {
            Node node = new Node(cur.val);
            node.next = cur.next;
            cur.next = node;
            cur = node.next;
        }
        cur = head;
        while (cur != null) {
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }
        Node old = head;
        Node newNode = head.next;
        Node res = head.next;
        while (newNode != null) {
            old.next = old.next.next;
            newNode.next = newNode.next == null ? null : newNode.next.next;
            // 往尾部挂节点
            old = old.next;
            newNode = newNode.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

14、环形链表(141)

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

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

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

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

思路：快慢指针，如果快慢指针相等代表有环

public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

15、环形链表 II(142)

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

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

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

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

思路：快慢指针相等确定有环，然后再用头结点和慢指针一步一步遍历相等的点就是入环的点。

public ListNode detectCycle(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast){
                // 有环
                ListNode pre = head;
                while (pre!=slow){
                    pre = pre.next;
                    slow = slow.next;
                }
                return pre;
            }
        }
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

16、重排链表(143)

题目：给定一个单链表 L：L0→L1→…→Ln-1→Ln ，
将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

给定链表 1->2->3->4, 重新排列为 1->4->2->3.
1

思路：快慢指针找到中点，然后将后面的反转，中断前后，最后遍历前后拼接进来。

public void reorderList(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode reverse = mid.next;
        mid.next = null;
        ListNode pre = null;
        while (reverse!=null){
            ListNode next = reverse.next;
            reverse.next = pre;
            pre = reverse;
            reverse = next;
        }
        while (head!=null && pre!=null){
            ListNode h1 = head.next;
            ListNode p1 = pre.next;
            head.next = pre;
            head = h1;
            pre.next = head;
            pre = 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

17、对链表进行插入排序(147)

题目：对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

插入排序算法：

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

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

思路：插入排序，每次从前到后遍历确定插入的位置。

   public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode pre = new ListNode(-1);
        pre.next = head;
        ListNode moved = head;
        ListNode cur = head.next;
        while (cur != null) {
            if (moved.val <= cur.val) {
                moved = moved.next;
                cur = cur.next;
            } else {
                ListNode prev = pre;
                while (prev.next.val <= cur.val){
                    prev = prev.next;
                }
                // 将链接上，把cur节点去掉，接上后面的
                moved.next = cur.next;
                // cur节点移动到前面位置
                cur.next = prev.next;
                prev.next = cur;
                cur = moved.next;
            }
        }
        return pre.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

18、排序链表(148)

题目：给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

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

思路：归并排序，注意尾tail作为末位判断

    public ListNode sortList(ListNode head) {
        return sort(head,null);
    }

    public ListNode sort(ListNode head,ListNode tail){
        // 当头==尾时，说明当前节点下面没有子树了。
        if (head == tail){
            return head;
        }
        // 找中点，然后合并，类似构建二叉树
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=tail && fast.next!=tail){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow;
        ListNode next = mid.next;
        mid.next = null;
        ListNode left = sort(head, mid);
        ListNode right = sort(next, tail);
        return merge(left, right);
    }

    /**
     * 合并两个升序链表
     * @param l1
     * @param l2
     */
    public ListNode merge(ListNode l1,ListNode l2){
        ListNode res = new ListNode(-1);
        ListNode cur = res;
        while (l1!=null && l2!=null){
            if (l1.val >= l2.val){
                cur.next = l2;
                l2 = l2.next;
            }else {
                cur.next = l1;
                l1 = l1.next;
            }
            cur = cur.next;
        }
        if (l1!=null){
            cur.next = l1;
        }
        if (l2!=null){
            cur.next = l2;
        }
        return res.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
42
43
44
45
46
47
48
49
50

19、相交链表(160)

题目：编写一个程序，找到两个单链表相交的起始节点。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7

思路：a+b = b+a

/**
     * 解题思路：
     * a1->a2->c1->c2->c3->b1->b2->b3->c1->c2->c3;
     * b1->b2->b3->c1->c2->c3->a1->a2->c1->c2->c3;
     * --------------------------------!-----------
     * a+b 和 b+a 如果有重合的那么肯定最后的几个元素就是重合的元素、 上面就是！处的c1是重复的
     *
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode a = headA;
        ListNode b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

20、移除链表元素(203)

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

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

思路：遍历，相等就删除

    public ListNode removeElements(ListNode head, int val) {
        if (head == null){
            return null;
        }
        ListNode res = new ListNode(-1);
        res.next = head;
        ListNode cur = res;
        while (cur!=null && cur.next!=null){
            ListNode next = cur.next;
            if (next.val == val){
                cur.next = next.next;
            }else {
                cur = cur.next;
            }
        }
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

21、反转链表(206)

题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

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

思路：反转链表

    public ListNode reverseList(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode cur = head;
        ListNode pre = null;
        while(cur!=null){
            ListNode 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

22、回文链表(234)

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

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

思路：先找中点，然后反转后面，然后遍历对比都相等，则是回文。

public static boolean isPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }

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

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

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    private static ListNode endOfFirstHalf(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // next和next.next能保证偶数链表中点出现在前面  1-2-3-4  2的位置  而 fast  fast.next的方式中点会出现在3的位置需要额外判断
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
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

23、删除链表中的节点(237)

题目：请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
1
2
3

思路：当前节点值是下一个节点的值，然后把下一个节点删除，这样就能达到效果了。

    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
1
2
3
4

24、奇偶链表(328)

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

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

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

思路：双节点，奇数节点和偶数节点。穿针引线。

public ListNode oddEvenList(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode odd = head;
        ListNode res = odd;
        ListNode even = head.next;
        ListNode evenTmp = even;
        while (even !=null && even.next!=null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenTmp;
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

25、430. 扁平化多级双向链表(430)

题目：多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给你位于列表第一级的头节点，请你扁平化列表，使所有结点出现在单级双链表中。

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：

输入的多级列表如下图所示：

  1---2---NULL
  |
  3---NULL
1
2
3
4
5
6
7
8
9

思路：这个就是广度优先遍历，使用Deque 队列。但是有个小坑，就是是一个双链表，要把结果的child置空，prev指向前驱。

public Node flatten(Node head) {
        if (head == null){
            return null;
        }
        Deque<Node> stack = new ArrayDeque<>();
        Node res = new Node(-1);
        Node ans = res;
        stack.push(head);
        while (!stack.isEmpty()){
            Node pop = stack.pop();
            if (pop.next!=null){
                stack.push(pop.next);
            }
            if (pop.child!=null){
                stack.push(pop.child);
            }
            // 指前后节点，child置空
            pop.next = null;
            pop.child = null;
            res.next = pop;
            pop.prev = res;
            res = res.next;
        }
        ans = ans.next;
        ans.prev = null;
        return 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

26、两数相加 II(445)

题目：给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 8 -> 0 -> 7
1
2

思路：这个需要遍历到尾，然后再加，再加就像两数相加一样。

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1!=null){
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2!=null){
            stack2.push(l2.val);
            l2 = l2.next;
        }
        ListNode cur = null;
        int add = 0;
        while (!stack1.isEmpty() || !stack2.isEmpty() || add !=0){
            int a = stack1.isEmpty()?0:stack1.poll();
            int b = stack2.isEmpty()?0:stack2.poll();

            int sum = a+b+add;
            add = sum / 10;
            ListNode node = new ListNode(sum%10);
            node.next = cur;
            cur = node;
        }
        return cur;
    }
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

27、设计链表(707)

题目：设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3
1
2
3
4
5
6
7

思路，类中定义一个链表，维护链表的数据

class MyLinkedList {
    ListNode head;
    int size;
    public MyLinkedList() {
        head = new ListNode(-1);
        size = 0;
    }
    public int get(int index) {
        if (index <0 ||  index>=size){
            return -1;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.next.val;
    }
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    public void addAtIndex(int index, int val) {
        if (index < 0 ){
            index = 0;
        }
        if (index > size){
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        ListNode node = new ListNode(val);
        node.next = cur.next;
        cur.next = node;
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index<0 || index>=size){
            return;
        }
        ListNode cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }
}
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

28、分隔链表(725)

题目：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。

这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。

返回一个符合上述规则的链表的列表。

举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

输入: 
root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]]
解释:
输入输出各部分都应该是链表，而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/split-linked-list-in-parts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12

思路：先分每个段几个元素然后从头往后遍历，将对应的元素放到返回数组里。

    public static ListNode[] splitListToParts(ListNode root, int k) {
        ListNode[] res = new ListNode[k];
        if (root == null){
            return res;
        }
        int[] arr = new int[k];
        ListNode loop = root;
        int len = 0;
        while (loop!=null){
            len++;
            loop = loop.next;
        }
        // 分配每个段几个元素
        for (int i = 0; i < len; i++) {
            arr[i%k]++;
        }
        ListNode cur = root;
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[i];
            ListNode nowNode = new ListNode(-1);
            nowNode.next = cur;
            ListNode tmpNode = nowNode;
            while (cur!=null && tmp>0){
                tmp--;
                cur = cur.next;
                tmpNode = tmpNode.next;
            }
            tmpNode.next = null;
            res[i] = nowNode.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

29、链表组件(817)

题目：给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。

同时给定列表 G，该列表是上述链表中整型值的一个子集。

返回列表 G 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 G 中）构成的集合。

输入: 
head: 0->1->2->3
G = [0, 1, 3]
输出: 2
解释: 
链表中,0 和 1 是相连接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一个组件，同理 [3] 也是一个组件，故返回 2。
1
2
3
4
5
6

思路：当前节点在G中出现且next节点在G中没出现就是组件的次数，G中所有的元素能构成多少个head中相连的子链表？

public int numComponents(ListNode head, int[] G) {
        if (head == null){
            return 0;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < G.length; i++) {
            map.put(G[i],null);
        }
        int res = 0;
        ListNode cur = head;
        while (cur!=null){
            if (map.containsKey(cur.val) && (cur.next==null||!map.containsKey(cur.next.val))){
                res++;
            }
            cur = cur.next;
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

30、链表的中间结点(876)

题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
注意，我们返回了一个 ListNode 类型的对象 ans，这样：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
1
2
3
4
5

思路：快慢双指针找中点。

    public ListNode middleNode(ListNode head) {
        if (head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while (fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
1
2
3
4
5
6
7
8
9
10
11
12

31、 链表中的下一个更大节点(1019)

题目：给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, … 。

每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。

返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。

输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
1
2

思路：求解下一个更大的值，这种就是用单调栈。1下一个比1大的是7，5下一个比它大的是9如果没有比自己大的就是0

    public int[] nextLargerNodes(ListNode head) {
        if (head == null){
            return new int[]{0};
        }
        List<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < list.size(); i++) {
            // 4,1,7,3,5
            while (!stack.isEmpty() && list.get(stack.peek())<list.get(i)){
                // 栈不为空，栈顶小于当前值。 栈里是 4，1 当前是7 那么1出栈(1在数组中的索引是1)，设置1的索引对应的下一个最大值为7。
                // 继续循环，栈里是4，当前是7 那么4出栈(4在数组中的索引是0)，设置0的索引对应的下一个最大值为7然后栈空或者下一个栈顶值小于7打破循环
                // 如果没有更大值就是默认值的0，如果数组是  9,1,7,3,5 那么9肯定不会出栈，9的索引0也不会被赋值
                Integer index = stack.pop();
                res[index] = list.get(i);
            }
            stack.push(i);
        }
        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

new Stack
for（遍历处理数组）{
    while（栈非空 && 达到预期条件）{ // 一般预期条件是栈顶 < 当前位置的值
        出栈并处理，保存到结果集
    }
    入栈（栈中保存数组的索引）
}
while(栈非空){   // 如果这道题就不需要这步了。因为不存在是0，0就是int的默认值
    出栈处理剩余栈内元素
}
1
2
3
4
5
6
7
8
9
10

32、从链表中删去总和值为零的连续节点(1171)

题目：给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
1
2
3

思路：需要两遍遍历，第一次遍历构建一个map，map的key是遍历过程中的sum和，value为遍历过程中的list. 第二次遍历，如果get(sum)能取到，就证明cur和get取出来的列表之间的和是0；那么cur.next = get.next;

public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> map = new HashMap<>();

        // 首次遍历建立 节点处链表和<->节点 哈希表
        // 若同一和出现多次会覆盖，即记录该sum出现的最后一次节点
        int sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            map.put(sum, d);
        }

        // 第二遍遍历 若当前节点处sum在下一处出现了则表明两结点之间所有节点和为0 直接删除区间所有节点
        sum = 0;
        for (ListNode d = dummy; d != null; d = d.next) {
            sum += d.val;
            d.next = map.get(sum).next;
        }

        return dummy.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

33、二进制链表转整数(1290)

题目：给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
1
2
3

思路：先反转，然后遍历链表，过程中记录要乘的基数。 按照2进制进行乘 加 就行了

    public int getDecimalValue(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        int loop = 1;
        int sum = 0;
        while (pre != null) {
            sum += pre.val * loop;
            pre = pre.next;
            loop *= 2;
        }
        return sum;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

34、二叉树中的列表(1367)

题目：给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

输入：head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
输出：true
解释：树中蓝色的节点构成了与链表对应的子路径。
1
2
3

思路：前序遍历树，然后head作为每个树节点的参照物。

public boolean isSubPath(ListNode head, TreeNode root) {
        if (head == null){
            return true;
        }
        if (root == null){
            return false;
        }
        return sub(head,root) || isSubPath(head,root.left) || isSubPath(head,root.right);
    }

    private boolean sub(ListNode head, TreeNode root){
        if (head == null){
            return true;
        }
        if (root == null){
            return false;
        }
        if (head.val != root.val){
            return false;
        }
        return sub(head.next,root.left) || sub(head.next,root.right);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

35、合并两个链表(1669)

题目：给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中第 a 个节点到第 b 个节点删除，并将list2 接在被删除节点的位置。

输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
解释：我们删除 list1 中第三和第四个节点，并将 list2 接在该位置。上图中蓝色的边和节点为答案链表。
1
2
3

思路：删list1 然后记录断点，list2遍历到尾，将其拼接上就行

public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode res = new ListNode(0);
        res.next = list1;
        ListNode cur = res;
        for (int i = 1; i < a; i++) {
            cur = cur.next;
        }
        ListNode pre = cur;
        int move = b-a;
        while (move >=0 && cur != null){
            move--;
            cur = cur.next;
        }
        pre.next = list2;
        ListNode cur2 = list2;
        while (cur2!=null && cur2.next!=null){
            cur2 = cur2.next;
        }
        cur2.next = cur.next;
        return res.next;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

36、交换链表中的节点(1721)

题目：给你链表的头节点 head 和一个整数 k 。

交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]
1
2

思路：找到对应节点，然后换值、

    public ListNode swapNodes(ListNode head, int k) {
        if (head == null){
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        for (int i = 1; i < k; i++) {
            fast = fast.next;
        }
        ListNode node1 = fast;
        while (fast!=null && fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        int tmp = node1.val;
        node1.val = slow.val;
        slow.val = tmp;
        return head;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以上：剩下的剑指offer和面试题都是重复的题了、