链表

链表常用虚拟头节点:

java

ListNode zero = new ListNode();
return zero.next;

归并

2. 两数相加 mid

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit.

请你将两个数相加，并以相同形式返回一个表示和的链表。
Add the two numbers and return the sum as a linked list.

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

JavaGo

Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode zero = new ListNode();
        ListNode p = zero;
        int carry = 0;
        while (l1 != null || l2 != null || carry > 0) {
            int a = 0, b = 0;
            if (l1 != null) {
                a = l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                b = l2.val;
                l2 = l2.next;
            }
            int sum = a + b + carry;
            carry = sum / 10;
            p = p.next = new ListNode(sum % 10);
        }
        return zero.next;
    }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    carry := 0
    zero := ListNode{}
    p := &zero
    for ; l1 != nil || l2 != nil || carry != 0; p = p.Next {
        a, b := 0, 0
        if l1 != nil {
            a = l1.Val
            l1 = l1.Next
        }
        if l2 != nil {
            b = l2.Val
            l2 = l2.Next
        }
        sum := a + b + carry
        p.Next = &ListNode{Val: (a + b + carry) % 10}
        carry = sum / 10
    }
    return zero.Next
}

21. 合并两个有序链表 easy

剑指 Offer 25. 合并两个排序的链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

解法 1 迭代

java

class Solution {
    public ListNode mergeTwoLists(ListNode n1, ListNode n2) {
        if (n1 == null) return n2;
        if (n2 == null) return n1;

        ListNode zero = new ListNode();
        ListNode curr = zero;

        while (true) {
            if (n1 == null) {
                curr.next = n2;
                break;
            }
            if (n2 == null) {
                curr.next = n1;
                break;
            }

            if (n1.val <= n2.val) {
                curr.next = n1;
                n1 = n1.next;
            } else {
                curr.next = n2;
                n2 = n2.next;
            }

            curr = curr.next;
        }

        return zero.next;
    }
}

解法 2 递归

两个链表头部值较小的一个节点的 next = merge 剩下元素的结果

java

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
    }
}

23. 合并 K 个升序链表 hard

给你一个链表数组，每个链表都已经按升序排列。
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

请你将所有链表合并到一个升序链表中，返回合并后的链表。
Merge all the linked-lists into one sorted linked-list and return it.

顺序合并的时间复杂度为 $O (n * k^{2})$ , 因为第 i 次合并的时间复杂度为 $O (i * n)$ , 共合并 k-1 次;

解法 1 优先队列

找一横截面中的最小值 $O (n k * l o g k)$ , 所有节点数量 nk, 堆大小为 k

java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));

        for (ListNode node : lists) {
            if (node != null) queue.add(node);
        }

        ListNode zero = new ListNode();
        ListNode p = zero;
        while (!queue.isEmpty()) {
            ListNode min = queue.remove();
            p.next = min;
            p = p.next;
            if (min.next != null) {
                queue.add(min.next);
            }
        }
        return zero.next;
    }
}

解法 2 归并

归并时间复杂度 $O (n k * l o g k)$ , 因为每一层的时间复杂度为合并次数乘合并开销, 最下层叶子节点合并次数=k/2, 合并开销=2n, 每一层的时间复杂度其实是相同的;

java

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    public ListNode merge(ListNode[] lists, int l, int r) {
        if (l == r) return lists[l];
        int mid = l + (r - l >> 1);
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l2.next, l1);
            return l2;
        }
    }
}

445. 两数相加 II mid

LCR 025. 两数相加 II

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

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

解法 1 从尾到头

用栈辅助

java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new LinkedList<>();
        Deque<Integer> stack2 = new LinkedList<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        int carry = 0;
        ListNode tail = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int val = 0;
            if (!stack1.isEmpty()) val += stack1.pop();
            if (!stack2.isEmpty()) val += stack2.pop();
            val += carry;
            carry = val / 10;
            val = val % 10;
            ListNode node = new ListNode(val);
            node.next = tail;
            tail = node;
        }
        return tail;
    }
}

解法 2 先反转

删除节点

删除就是找到节点的前一个节点, 删掉节点

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

LCR 021. 删除链表的倒数第 N 个结点
剑指 Offer 22. 链表中倒数第 k 个节点
剑指 Offer II 021. 删除链表的倒数第 n 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
Given the head of a linked list, remove the nth node from the end of the list and return its head.

解法
本题有多种解法:

可以直接求得倒数第 n 个节点的索引(L-n+1);
可以用栈, pop 第 n 个时, 删掉;
可以双指针;

双指针的间隔是固定的, 可以根据一个指针的结束条件定位到另一个的位置;
这里需要关注 2 个点: 当快指针第一次停止的时候, 停在哪; 当结束的时候, 快指针停在哪;
结束的时候, 慢指针停在倒数第 n+1 位, 快指针停在第 0 位(null)

java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode zero = new ListNode();
        zero.next = head;
        ListNode n1 = zero;
        // 快指针停在第n+1位, 慢指针停在第0位
        for (int i = 0; i <= n; i++) {
            n1 = n1.next;
        }
        ListNode n2 = zero;
        // 快指针停在第0位, 慢指针停在第n+1位
        while (n1 != null) {
            n1 = n1.next;
            n2 = n2.next;
        }
        n2.next = n2.next.next;
        return zero.next;
    }
}

83. 删除排序链表中的重复元素 mid

给定一个已排序的链表的头 head，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

多个重复的多次删除

java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            if (cur.val == cur.next.val) cur.next = cur.next.next;
            else cur = cur.next;
        }
        return head;
    }
}

203. 移除链表元素 easy

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

java

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode zero = new ListNode();
        zero.next = head;
        ListNode p = zero;
        while (p.next != null) {
            if (p.next.val == val) p.next = p.next.next;
            // 删掉后停住
            else p = p.next;
        }
        return zero.next;
    }
}

237. 删除链表中的节点 mid

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node。你将无法访问第一个节点 head。

链表的所有值都是唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。

解法把 next 删掉

java

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }
}

重排

分析一下每次操作的关系即可
设置多个 temp 指针会比较方便

24. 两两交换链表中的节点 mid

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

解法 1 迭代

java

class Solution {
    public ListNode swapPairs(ListNode p) {
        ListNode zero = new ListNode();
        zero.next = p;
        ListNode n0 = zero;
        // p 是迭代过程中的定位指针
        while (p != null && p.next != null) {
            ListNode n1 = p;
            ListNode n2 = p.next;
            ListNode n3 = p.next.next;
            n0.next = n2;
            n1.next = n3;
            n2.next = n1;

            n0 = n1;
            p = n3;
        }
        return zero.next;
    }
}

解法 2 递归

从最头部的 2 对开始递归

java

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = head.next;
        head.next = this.swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

143. 重排链表 mid

LCR 026. 重排链表

给定一个单链表 L 的头节点 head，单链表 L 表示为：

0, 1, ... n-1, n

请将其重新排列后变为：

0, n, 1, n-1, L2, n-2 ...

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

需要找到中点, 反转后半段, 再归并

解法 1: 栈做法

java

class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head, p2 = head;
        // 中点 或 偏右
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p2 = p2.next;
        }
        Deque<ListNode> stack = new ArrayDeque<>();
        while (p2 != null) {
            stack.push(p2);
            p2 = p2.next;
        }
        ListNode zero = new ListNode();
        ListNode n = zero;
        // 后半段一定不短于前半段
        while (!stack.isEmpty()) {
            n.next = head;
            head = head.next;
            n = n.next;
            n.next = stack.pop();
            n = n.next;
        }
        n.next = null;
        head = zero.next;
    }
}

解法 2: 反转合并

合并部分好好看看

java

class Solution {
    public void reorderList(ListNode head) {
        ListNode p1 = head, p2 = head;
        ListNode p0 = null;
        // 找中点
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p0 = p2;
            p2 = p2.next;
        }
        if (p0 == null) return;
        // 断开
        p0.next = null;
        // p2: 中点 或 偏右
        // 反转
        ListNode pre = null;
        ListNode n = p2;
        while (n != null) {
            ListNode next = n.next;
            n.next = pre;
            pre = n;
            n = next;
        }

        ListNode a = head;
        ListNode b = pre;
        // 合并 head, pre
        // 将副链表的头插入到主链表的next
        while (a != null) {
            ListNode aNext = a.next;
            a.next = b;
            ListNode bNext = b.next;
            if (aNext != null) b.next = aNext;
            a = aNext;
            b = bNext;
        }
    }
}

148. 排序链表 mid

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

只有快排堆排归并的时间复杂度为 $O (n l o g n)$

归并排序 可以自顶向下归并或者自底向上归并, 自顶向下, 需要将链表二分递归, 然后 merge; 空闲复杂度 $O (n l o g n)$
自底向上, 将链表拆成若干个长度为 subLen 子链表, 初始 subLen = 1, 然后两两 merge;

java

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return head;
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        ListNode zero = new ListNode(0, head);
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode pre = zero, curr = zero.next;
            // 第1步, 拆; 第2步, merge;
            while (curr != null) { // 分段操作
            // subLen1, subLen2, merge
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode head2 = curr.next;
                // 断开
                curr.next = null;
                curr = head2;
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                ListNode nxt = null;
                if (curr != null) {
                    nxt = curr.next;
                    // 断开
                    curr.next = null;
                }
                ListNode merged = merge(head1, head2);
                pre.next = merged;
                // 尾部,笨做法
                while (pre.next != null) {
                    pre = pre.next;
                }
                curr = nxt;
            }
        }
        return zero.next;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode zero = new ListNode(0);
        ListNode p0 = zero, p1 = head1, p2 = head2;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                p0.next = p1;
                p1 = p1.next;
            } else {
                p0.next = p2;
                p2 = p2.next;
            }
            p0 = p0.next;
        }
        if (p1 != null) {
            p0.next = p1;
        } else if (p2 != null) {
            p0.next = p2;
        }
        return zero.next;
    }
}

328. 奇偶链表 mid

给定单链表的头节点 head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

第一个节点的索引被认为是奇数，第二个节点的索引为偶数，以此类推。

请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。

你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。

先拆成 2 条, 然后在连起来
注意: while 条件是 even
如果 while 条件中是 odd, 以 odd 结尾时, 循环中会空指针

java

class Solution {
    public ListNode oddEvenList(ListNode oddHead) {
        if (oddHead == null) return null;
        ListNode evenHead = oddHead.next;
        ListNode odd = oddHead, even = oddHead.next;
        // o -> e -> o -> e
        // 必须用 even
        while (even != null && even.next != null) {
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return oddHead;
    }
}

拆分

725. 分隔链表 mid

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

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

返回一个由上述 k 部分组成的数组。

拆成桶, 计算每个桶的长度, 遍历 table

java

class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode node = head;
        ListNode[] res = new ListNode[k];
        int cnt = 0;
        while (node != null) {
            cnt++;
            node = node.next;
        }
        int size = cnt / k;
        int mod = cnt % k;
        node = head;

        for (int i = 0; i < k && node != null; i++) {
            res[i] = node;
            // 先把mod分散
            int curSize = size + (mod-- > 0 ? 1 : 0);
            for (int j = 0; j < curSize - 1; j++) {
                node = node.next;
            }
            ListNode next = node.next;
            node.next = null;
            node = next;
        }
        return res;
    }
}

找节点

876. 链表的中间结点 easy

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

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

这种分奇偶, 思考下应该停在哪

java

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

708. 排序的循环链表 mid

LCR 029. 循环有序列表的插入

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

如果大于最大值或小于最小值, 插入
注意一下全是相同元素的情况

java

class Solution {
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node(insertVal);
            head.next = head;
            return head;
        }
        Node node = head.next;
        while (node != head) {
            if (insertVal >= node.val && insertVal <= node.next.val)
                break;
            if (node.val > node.next.val && (insertVal >= node.val || insertVal <= node.next.val))
                break;
            node = node.next;
        }
        // 全是重复元素的情况也会在这处理
        Node next = node.next;
        node.next = new Node(insertVal);
        node.next.next = next;
        return head;
    }
}

构造

138. 随机链表的复制 mid

剑指 Offer 35. 复杂链表的复制

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

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

递归, 用 map 映射新老链表

java

class Solution {
    Map<Node, Node> cache = new HashMap<>();

    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (!cache.containsKey(head)) {
            Node newNode = new Node(head.val);
            cache.put(head, newNode);
            newNode.next = copyRandomList(head.next);
            newNode.random = copyRandomList(head.random);
        }
        return cache.get(head);
    }
}

找交点

141. 环形链表 easy

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

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

解法快慢指针

不用担心会错过, 它们必然相遇

Java

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode n1 = head;
        ListNode n2 = head;
        do {
            if (n1 == null || n1.next == null) return false;
            n1 = n1.next.next;
            n2 = n2.next;
        } while (n1 != n2);

        return true;
    }
}

142. 环形链表 II mid

LCR 022. 环形链表 II

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

解法快慢指针

a--b--c 是步数
a: 柄
b+c: 环
a+b+n(b+c) = 2(a+b)
a+b = n(b+c)
a = n(cycle) - b
在 b 点第 1 次相遇, 在 a 的末端第 2 次相遇

Java

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode n1 = head;
        ListNode n2 = head;
        do {
            if (n1 == null || n1.next == null) return null;
            n1 = n1.next.next;
            n2 = n2.next;
        } while (n1 != n2);
        // 他们将在柄环交界处重逢
        n2 = head;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
}

160. 相交链表 easy

LCR 023. 相交链表
剑指 Offer 52. 两个链表的第一个公共节点剑指 Offer II 023. 两个链表的第一个重合节点

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

解法 1 交换指针

不会出现死循环, 最后会同时到达尾端

java

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
        }
        return p1;
    }
}

解法 2 记录差值

如果链表相交, 尾部一定是同 1 个节点; 分别让 2 条链表的开始到尾部的长度相等, 一定相遇

java

class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        ListNode p1 = headA;
        ListNode p2 = headB;

        while (nodeA.next != null || nodeB.next != null) {
            if (nodeA.next != null) nodeA = nodeA.next;
            else p2 = p2.next;

            if (nodeB.next != null) nodeB = nodeB.next;
            else p1 = p1.next;
        }
        // 不同尾
        if (nodeA != nodeB) return null;

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

反转

206. 反转链表 easy

LCR 024. 反转链表
剑指 Offer 24. 反转链表剑指 Offer II 024. 反转链表

不需要 zero, 因为返回的不是头节点
有递归的方法, 相对而言更啰嗦

java

class Solution {
    public ListNode reverseList(ListNode node) {
        ListNode pre = null;
        while (node != null) {
            ListNode next = node.next;
            node.next = pre;
            pre = node;
            node = next;
        }
        return pre;
    }
}

234. 回文链表 easy

LCR 027. 回文链表

给你一个单链表的头节点 head，请你判断该链表是否为回文链表。

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

解法 1 复制到数组

解法 2 递归

维护 left, 利用递归栈

java

class Solution {
    private ListNode left;

    public boolean isPalindrome(ListNode head) {
        left = head;
        return check(head);
    }

    private boolean check(ListNode head) {
        if (head != null) {
            if (!check(head.next)) return false;
            if (head.val != left.val) return false;
            left = left.next;
        }
        return true;
    }
}

解法 3 反转链表

先快慢指针找到偏右中点, 然后反转, 从两端向中间对比, 最后反转复原

java

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head.next == null) return true;
        ListNode p1 = head;
        ListNode p2 = head;
        int cnt = 0;
        // 1 -> 2 -> 3  ==>  1 -> 2 <- 3
        // 1 -> 2 -> 3 -> 4 ==> 1 -> 2 -> 3 <- 4
        while (p1 != null && p1.next != null) {
            p1 = p1.next.next;
            p2 = p2.next;
            cnt++;
        }

        ListNode head2 = revert(p2);

        for (int i = 0; i < cnt; i++) {
            if (head.val == head2.val) {
                head2 = head2.next;
                head = head.next;
            } else {
                revert(p2);
                return false;
            }
        }
        revert(p2);
        return true;
    }

    // 反转
    private ListNode revert(ListNode head) {
        ListNode node = head;
        ListNode pre = null;
        while (node != null) {
            ListNode temp = node.next;
            node.next = pre;
            pre = node;
            node = temp;
        }
        return pre;
    }
}

压缩列表展开

430. 扁平化多级双向链表 mid

LCR 028. 扁平化多级双向链表

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

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

取到子链表的头尾, 连在父链上

java

class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
}

class Solution {
    public Node flatten(Node head) {
        flattenReturnTail(head);
        return head;
    }

    public Node flattenReturnTail(Node head) {
        if (head == null) return null;
        Node pre = null;
        while (head != null) {
            if (head.child != null) {
                Node next = head.next;

                Node childHead = head.child;
                Node childTail = flattenReturnTail(head.child);

                head.next = childHead;
                childHead.prev = head;
                head.child = null;

                childTail.next = next;
                if (next != null) next.prev = childTail;

                head = childTail;
            }
            pre = head;
            head = head.next;
        }
        return pre;
    }
}

链表 ​

归并 ​

2. 两数相加 mid ​

21. 合并两个有序链表 easy ​

23. 合并 K 个升序链表 hard ​

445. 两数相加 II mid ​

删除节点 ​

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

83. 删除排序链表中的重复元素 mid ​

203. 移除链表元素 easy ​

237. 删除链表中的节点 mid ​

重排 ​

24. 两两交换链表中的节点 mid ​

143. 重排链表 mid ​

148. 排序链表 mid ​

328. 奇偶链表 mid ​

拆分 ​

725. 分隔链表 mid ​

找节点 ​

876. 链表的中间结点 easy ​

708. 排序的循环链表 mid ​

构造 ​

138. 随机链表的复制 mid ​

找交点 ​

141. 环形链表 easy ​

142. 环形链表 II mid ​

160. 相交链表 easy ​

反转 ​

206. 反转链表 easy ​

234. 回文链表 easy ​

压缩列表展开 ​

430. 扁平化多级双向链表 mid ​

链表

归并

2. 两数相加 mid

21. 合并两个有序链表 easy

23. 合并 K 个升序链表 hard

445. 两数相加 II mid

删除节点

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

83. 删除排序链表中的重复元素 mid

203. 移除链表元素 easy

237. 删除链表中的节点 mid

重排

24. 两两交换链表中的节点 mid

143. 重排链表 mid

148. 排序链表 mid

328. 奇偶链表 mid

拆分

725. 分隔链表 mid

找节点

876. 链表的中间结点 easy

708. 排序的循环链表 mid

构造

138. 随机链表的复制 mid

找交点

141. 环形链表 easy

142. 环形链表 II mid

160. 相交链表 easy

反转

206. 反转链表 easy

234. 回文链表 easy

压缩列表展开

430. 扁平化多级双向链表 mid