励志：

🚩 半身浸江，全身如林，所谓万丈深渊，下去也是前程万里。我启程了，你呢?

一、单向链表

1. 链表操作

1.1 链表旋转

题：61. 旋转链表

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

解：

📖 解题思路：

得到链表长度len
指针p指向第n - k节点
修改head，p，tail 的next指向

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || k == 0) return head; // 判空
        ListNode tail = head;
        // 链表长度
        int len = 1; 
        while(tail.next != null){
           tail = tail.next; 
           len ++;
        }
        // 第n-K节点
        k %= len;         
        ListNode p = head;
        for(int i = 1; i <= len - k - 1; i ++) p = p.next;
        // 修改指针指向
        tail.next = head;
        head = p.next;
        p.next = null;
        return head;
    }
}

时间复杂度：时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。
空间复杂度：O(1)，我们只需要常数的空间存储若干变量。

题：25. K 个一组翻转链表

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

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

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

进阶：

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

列表中节点的数量在范围 sz 内
1 <= sz <= 5000
0 <= Node.val <= 1000
1 <= k <= sz

解：

📖 解题思路： 反转链表

首加一个空（减少判空，便于return）
翻转指针（pre，start，end，next）
反转链表模板（三人行）

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 首加一个空节点(1.减少判断 2.返回节点)
        ListNode preTemp = new ListNode();
        preTemp.next = head;

        // 翻转区间（start，end）
        ListNode pre = preTemp;
        ListNode start = pre;
        ListNode end = pre;
        ListNode next = end.next;
        
        while(end.next != null) {
            // 判断是否还可以继续翻转
            for(int i = 0; i < k; i ++){
                end = end.next;
                if(end == null) return preTemp.next;
            } 
            start = pre.next;
            next = end.next;
            // 断链
            end.next = null;
            // 接链（此时end在前，start在后）
            pre.next = reverse(start);           
            start.next = next;
            // start, end重新归位
            pre = start;
            end = pre;
        }
        return preTemp.next;
    }

    // 反转链表模板
    ListNode reverse(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度：O(n)，其中 n 为链表的长度。
空间复杂度：O(1)，常数个变量。

1.2 链表相交

题：面试题 02.07. 链表相交

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

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

在这里插入图片描述
题目数据保证整个链式结构中不存在环。

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

示例 1：

在这里插入图片描述

输入：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：
在这里插入图片描述

输入：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：
在这里插入图片描述

输入：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 = 2+1

没有交点的情况可以约化为交点为 None 的情况。（即将两链表末端的 None 看作交点）
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

时间复杂度 O(a + b) ：最差情况下（即 |a - b| = 1 , c = 0），此时需遍历 a + b 个节点。
空间复杂度 O(1) ：节点指针 A , B 使用常数大小的额外空间。

以下题目一样，不再赘述了。

题：剑指 Offer 52. 两个链表的第一个公共节点

题：160. 相交链表

题：剑指 Offer II 023. 两个链表的第一个重合节点

📖 另解：哈希

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visit = new HashSet<>();
        // 遍历A
        ListNode temp = headA;
        while(temp != null) {
            visit.add(temp);
            temp = temp.next;
        }
        // 遍历B
        temp = headB;
        while(temp != null) {
            if(visit.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

1.3 链表归并

题：21. 合并两个有序链表

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

示例 1：
在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

解：

📖 解题思路：递归
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // l1 or 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;
        }
    }
}

时间复杂度：O(n+m)，其中n，m分别为链表长度。
空间复杂度：O(n+m)，其中n，m分别为链表长度。

📖 另解：迭代

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode preTmp = new ListNode(); // 伪头结点
        ListNode node = preTmp;
        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                node.next = l1;
                l1 = l1.next;
            }else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        // 合并未完成的
        node.next = l1 == null ? l2 : l1;
        return preTmp.next;
    }
}

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

题：23. 合并K个升序链表

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

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

示例 1：

输入：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：

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

示例 3：

输入：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

解：

📖 解题思路：朴素解法（正常合并）

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode res = null;
        for(ListNode list : lists) {
            res = mergeTwoList(res, list);
        }
        return res;
    }
    ListNode mergeTwoList(ListNode A, ListNode B) {
        // 伪头结点, 虚拟链
        ListNode preTemp = new ListNode();
        // 指针
        ListNode node = preTemp;
        while(A != null && B != null) {
            if(A.val < B.val) {
                node.next = A;
                A = A.next;
            }else {
                node.next = B;
                B = B.next;
            }
            node = node.next;
        }
        node.next = A != null ? A : B;
        return preTemp.next;
    }
}

时间复杂度：O（k^2 * n）
空间复杂度：O（1）

📖 解题思路：二分

二分模板详情看这儿

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }
    ListNode merge(ListNode[] lists, int l, int r) {
        // 出口
        if(l == r) return lists[l]; // 这个很重要
        if(l > r) return null;
        // 递归划分
        int m = (l + r) >> 1;
        ListNode A = merge(lists, l, m);
        ListNode B = merge(lists, m + 1, r);
        // 合并
        return mergeTwoList(A, B);
    }
    ListNode mergeTwoList(ListNode A, ListNode B) {
        // 伪头结点, 虚拟链
        ListNode preTemp = new ListNode();
        // 指针
        ListNode node = preTemp;
        while(A != null && B != null) {
            if(A.val < B.val) {
                node.next = A;
                A = A.next;
            }else {
                node.next = B;
                B = B.next;
            }
            node = node.next;
        }
        node.next = A != null ? A : B;
        return preTemp.next;
    }
}

时间复杂度：O（kn * log k）二分使用后 k → log k
空间复杂度：O（log k）二分使用后，递归栈空间log k

📖 解题思路：优先队列

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 优先队列(小顶堆)(先储存各链表的头结点)
        Queue<ListNode> priQueue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for(ListNode list : lists) {
            if(list != null) { // 注意这里不为空
                priQueue.offer(list);
            }           
        }
        // 伪头结点
        ListNode preTemp = new ListNode();
        // 指针
        ListNode temp = preTemp;
        // 遍历堆
        while(!priQueue.isEmpty()) {
            ListNode min = priQueue.poll();
            temp.next = min;
            temp = temp.next;
            if(min.next != null) {
                priQueue.offer(min.next);
            }
        }
        return preTemp.next;
    }
}

时间复杂度：O（kn * log k）
空间复杂度：O（log k）

题：剑指 Offer II 078. 合并排序链表

题：143. 重排链表

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

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000

解：

📖 解题思路：双指针 + 线性表

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;
        // 线性表
        List<ListNode> list = new ArrayList<>();
        ListNode temp = head;
        while(temp != null) {
            list.add(temp);
            temp = temp.next;
        }
        // 双指针
        int i = 0, j = list.size() - 1;
        while(i < j) {
            list.get(i).next = list.get(j);
            i ++;
            if(i == j) break;
            list.get(j).next = list.get(i);
            j --;
        }
        list.get(i).next = null;
    }
}

时间复杂度：O（N），N为链表的节点数，遍历链表
空间复杂度：O（N），N为链表的节点数，线性表占用空间N

解题思路：寻找链表中点 + 链表逆序 + 合并链表

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null) return;

        ListNode mid = midNode(head);
        ListNode l2 = reverList(mid.next);
        mid.next = null;
             
        mergeList(head, l2);
    }
    // 找中点（快慢指针）
    ListNode midNode(ListNode node) {
        ListNode p = node;
        ListNode q = node;
        while(q.next != null && q.next.next != null) {
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
    // 反转链表（三人行）
    ListNode reverList(ListNode node) {
        ListNode pre = null;
        ListNode cur = node;
        while(cur != null) {
            // 松手先保存
            ListNode nextTemp = cur.next;
            // 松手
            cur.next = pre;
            // 指针前移
            pre = cur;
            cur = nextTemp;
        }
        return pre;
    }
    // 合并链表
    void mergeList(ListNode A, ListNode B) {
        ListNode A_next;
        ListNode B_next;
        while(A != null && B != null) {
            A_next = A.next;
            A.next = B;
            A = A_next;

            B_next = B.next;
            B.next = A;
            B = B_next;
        }
    }
}

时间复杂度：O（N）， N为链表节点
空间复杂度：O（1）

1.4 链表排序

题：148. 排序链表

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

进阶：

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

解：

解题思路：自顶向下归并排序

找中点（快慢双指针）
链表排序
合并排序链表

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }
    // 链表排序(二分法)
    public ListNode sortList(ListNode head, ListNode tail) {
        // 递归出口(节点个数 == 0 、1)
        if(head == null || head.next == null) return head;

        ListNode mid = mid(head);
        ListNode node = mid.next; // 松手前先保存
        mid.next = null; 

        ListNode L1 = sortList(head, mid);
        ListNode L2 = sortList(node, tail);
        return merge(L1, L2);
    }
    // 找中点
    ListNode mid(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q.next != null && q.next.next != null) {
            p = p.next;
            q = q.next.next;          
        }
        return p;
    }
    // 链表合并(递归法)
    ListNode merge(ListNode A, ListNode B) {

        if(A == null) return B;
        if(B == null) return A;

        if(A.val < B.val) {
            A.next = merge(A.next, B);
            return A;
        }else {
            B.next = merge(A, B.next);
            return B;
        }
    }
}

时间复杂度：O（N logN），N为链表长度
空间复杂度：O（logN），N为链表长度

解题思路：自底向上归并排序

链表长度
链表拆分与合并（步长 << 2 切分））

注意：拆分保证两条链独立，并临时保存要拼接的节点 ==（分手先保存。合并要纯粹）==

在这里插入图片描述
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 链表为空或链表只剩一个节点
        if(head == null || head.next == null) return head;
        // 伪头结点
        ListNode node = new ListNode();
        node.next = head;
        // 链表长度
        int len = 0;
        ListNode temp = head;
        while(temp != null) {
            len ++;
            temp = temp.next;
        }
        // 遍历
        for(int i = 1; i < len; i <<= 1) { // i 为步数，步数指数翻倍
            // 即将分手的pre，cur(指针)
            ListNode pre = node;
            ListNode cur = node.next;           
            while(cur != null) { // 还能分手吗？
                // 分割链, A链， B链
                ListNode A = cur;
                ListNode B = splitList(A, i);
                // cur先复位，再合并对接（合并要保证两链独立） 
                cur = splitList(B, i); // cur 复位               
                pre.next = mergeList(A, B); // pre 对接               
                while(pre.next != null) { // pre复位
                    pre = pre.next;
                }
            }           
        }
        return node.next;
    }
    // 分割得到链表A，B，拿到B的头结点
    ListNode splitList(ListNode head, int step) {
        if(head == null) return null;
        for(int i = 1; i < step && head.next != null; i ++) {
            head = head.next;
        }
        // 保存
        ListNode res = head.next;
        // 松手
        head.next = null;
        return res;
    }
    // 合并，迭代法
    ListNode mergeList(ListNode A, ListNode B) {
        // 伪头结点
        ListNode preTemp = new ListNode();
        // 哨兵
        ListNode node = preTemp;
        while(A != null && B != null) {
            if(A.val < B.val) {
                node.next = A;
                A = A.next;
            }else {
                node.next = B;
                B = B.next;
            }
            node = node.next;
        }
        // 判空
        node.next = A != null ? A : B;
        return preTemp.next; 
    }
}

时间复杂度：O（N logN）
空间复杂度：O（1）

题：剑指 Offer II 077. 链表排序

1.5 链表回文

题：234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

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

解：

解题思路：

找中点
翻转一半
比对
还原（可有可无）

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null || head.next == null) return true;
        // 找中点 1=>1 123=>2 1234=>2
        ListNode A_end = mid(head);
        ListNode B_start = A_end.next;
        A_end.next = null;
        // 翻转后半部分
        B_start = reverse(B_start);
        // 比对
        boolean res = compare(head, B_start);
        // 还原
        A_end.next = reverse(B_start);
        return res;
    }
    // 链表找中点，快慢指针法
    ListNode mid(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while(q.next != null && q.next.next != null) {
             p = p.next;
             q = q.next.next;
        }
        return p;
    }
    // 链表反转模板
    ListNode reverse(ListNode head) { // 三人行模板
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next; // 松手先保存
            cur.next = pre;
            pre = cur; // 归位
            cur = temp;
        }
        return pre;
    }
    // 链表比对模板(len(B) <= len(A))
    boolean compare(ListNode A, ListNode B) {
        while(B != null) {
            if(A.val != B.val) return false;
            A = A.next;
            B = B.next;
        }
        return true;
    }
}

时间复杂度：O（N）：N为链表长度
空间复杂度：O（1）：只修改链表的指向

题：剑指 Offer II 027. 回文链表

题：面试题 02.06. 回文链表

1.6 链表逆序

题：剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

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

限制：

0 <= 链表长度 <= 10000

解：

解题思路：辅助栈

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        while(head != null) {
            stack.push(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i ++) {
            res[i] = stack.pop();
        }
        return res;
    }
}

时间复杂度：O（N），遍历链表
空间复杂度：O（N）, 额外使用一个栈来存储链表中的每一个节点

另解：递归（与上面解法本质一样）

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[list.size()];
        for(int i = 0; i < res.length; i ++) {
            res[i] = list.get(i);
        }
        return res;
    }
    void recur(ListNode head) {
        if(head == null) return;        
        recur(head.next); // 先递归
        list.add(head.val);  // 然后添加   
    }
}

题：剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:

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

限制：

0 <= 节点个数 <= 5000

解：

解题思路：反转模板

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 三人行
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next; // 松手
            cur.next = pre;
            // 归位
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

时间复杂度：O（N）：遍历链表，N为链表长度
空间复杂度：O（1）：指针常量

另解：递归

规避递归细节，找递推公式！
eg. 1->2->3->null ==> null<-1<-2<-3

fun（node1）= fun（node2） + ？
？ = 2->1 + 1->null

AC代码：

public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {  //终止条件并不难想
            return head;
        }
        ListNode node = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return node;  //按上面的例子，F(node=1)和F(node=2)它俩反转后的头节点是同一个
    }

题：206. 反转链表

题：剑指 Offer II 024. 反转链表

题：445. 两数相加 II

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

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

示例1：
在这里插入图片描述

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

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

提示：

链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0 

进阶：如果输入链表不能修改该如何处理？换句话说，不能对列表中的节点进行翻转。

解：

解题思路：栈

逆序=>栈 O（N）、反转 O（1）
进位判断（/10=进位 %10=本位）
双指针倒指（null <- A <- B ...）

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<Integer> A = new Stack<>();
        Stack<Integer> B = new Stack<>();
        // 入栈
        while(l1 != null) {
            A.push(l1.val);
            l1 = l1.next;
        }
        while(l2 != null) {
            B.push(l2.val);
            l2 = l2.next;
        }
        ListNode res = null;
        int nextDigit = 0; // 进位       
        while(!A.isEmpty() || !B.isEmpty() || nextDigit != 0) {
            int a = A.isEmpty() ? 0 : A.pop(); // 弹出先判空，防止空指针
            int b = B.isEmpty() ? 0 : B.pop();
            int c = a + b + nextDigit;
            nextDigit = c / 10;
            c = c % 10;
            ListNode temp = new ListNode(c);
            temp.next = res; // 放在第一位
            res = temp; // res指针前移
        }
        return res;
    }
}

时间复杂度：O（max（m，n））：m，n分别为链表a，b长度，最坏遍历完最长链表
空间复杂度：O（m + n）：m，n分别为链表a，b长度，最坏链表每次相加后都进位

另解：反转链表

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 反转l1，l2
        l1 = reverse(l1);
        l2 = reverse(l2);
        // 正向指针
        ListNode preHead = new ListNode(); // 伪头结点
        ListNode node = preHead; // 指针，操作链表
        int nextDigit = 0; // 进位
        // 链表相加
        while(l1 != null || l2 != null || nextDigit != 0) {
            int sum = nextDigit;
            if(l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if(l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            nextDigit = sum / 10;
            sum = sum % 10;
            // 进位规则：往右进位
            ListNode temp = new ListNode(sum);
            node.next = temp;
            node = node.next;
        }
        return reverse(preHead.next);
    }
    ListNode reverse(ListNode head) {
        // 三人行模板
        ListNode pre = null; 
        ListNode cur = head;
        while(cur != null) {
            ListNode temp = cur.next; // 松手先保存
            cur.next = pre;
            // 指针归位
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

题：剑指 Offer II 025. 链表中的两数相加

题：92. 反转链表 II

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

示例 1：
在这里插入图片描述

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

示例 2：

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

提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n 

进阶： 你可以使用一趟扫描完成反转吗？

解：

解题思路：穿针引线法

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 伪头节点
        ListNode preHead = new ListNode();
        preHead.next = head;
        // leftNode(2) -> start(3) -> end(5) -> rightNode(6)
        ListNode leftNode = preHead;
        for(int i = 0; i < left - 1; i ++) {
            leftNode = leftNode.next;
        }
        ListNode start = leftNode.next;
        ListNode end = leftNode;
        for(int i = 0; i < right - left + 1; i ++) {
            end = end.next;
        }
        ListNode rightNode = end.next;
        // 断链
        leftNode.next = null;
        end.next = null;
        // 反转 + 拼接
        leftNode.next = reverse(start);
        start.next = rightNode;

        return preHead.next;
    }
    // 反转模板
    ListNode reverse(ListNode head) {
        // 三人行模板
        ListNode pre = null; 
        ListNode cur = head;
        while(cur != null) {
            // 松手先保存
            ListNode temp = cur.next;
            cur.next = pre;
            // 指针归位
            pre = cur; 
            cur = temp;
        }
        return pre;
    }
}

时间复杂度：O（N）N为链表长度，最坏长度遍历整个链表。
空间复杂度：O（1）用到四个指针常量。

另解：头插法 + 穿针引线

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 伪头节点
        ListNode dummyNode = new ListNode();
        dummyNode.next = head;
        // 三人行  pre(), cur(), next();
        ListNode pre = dummyNode;
        for(int i = 0; i < left - 1; i ++) {
            pre = pre.next;
        }
        // 头插法
        ListNode cur = pre.next;
        ListNode next;
        for(int i = 0; i < right - left; i ++) { // 第一个不需要操作，所以直接len(r-f)-1
            next = cur.next; 
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }
        return dummyNode.next;
    }
}

2. 链表结点操作

2.1 链表结点删除

题：剑指 Offer 18. 删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意： 此题对比原题有改动

示例 1:

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

示例 2:

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

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

解：

解题思路：双指针

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if(head.val == val) return head.next;
        // cur:待删除的节点  pre:删除节点的上一个
        ListNode pre = head;
        ListNode cur = pre.next;
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        if(cur != null) pre.next = cur.next;
        return head;
    }
}

时间复杂度：O（N）
空间复杂度：O（1）

题：237. 删除链表中的节点

请编写一个函数，用于删除单链表中某个特定节点。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问要被删除的节点。

题目数据保证需要删除的节点不是末尾节点。

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

示例 3：

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

示例 4：

输入：head = [0,1], node = 0
输出：[1]

示例 5：

输入：head = [-3,5,-99], node = -3
输出：[5,-99]

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是唯一的
需要删除的节点 node 是 链表中的一个有效节点 ，且 不是末尾节点

解：

解题思路：狸猫换太子

我们不知道前一节点，无法直接删除操作，那就将要删除节点的next节点==赋值==给删除节点，==转化为删除next节点==。

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        // 将自己复制成下一个节点
        node.val = node.next.val;
        // 自己的下一节点指向下下个
        node.next = node.next.next;
    }
}

时间复杂度：O（1）
空间复杂度：O（1）

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

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

示例 1：
在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

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

解：

解题思路：双指针

伪头结点，前后指针
终点：前=待删除结点上一个后=null（末尾）
起点：前 =伪头结点后=伪 + n

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode();
        dummy.next = head;
        // 前后指针
        ListNode p = dummy;
        ListNode q = head;
        for(int i = 0; i < n; i ++) {
            q = q.next;
        }
        while(q != null) {
            p = p.next;
            q = q.next;
        }
        p.next = p.next.next;
        return dummy.next;
    }
}

时间复杂度：O（N）遍历链表，N为链表长度
空间复杂度：O（1）指针常量

题：剑指 Offer II 021. 删除链表的倒数第 n 个结点

题：237. 删除链表中的节点

题：82. 删除排序链表中的重复元素 II

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

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

解：

解题思路：双指针

在这里插入图片描述

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1, head);
        // 双指针
        ListNode p = dummy;
        ListNode q = head;
        while(q != null) {
            boolean flag = false;
            while(q.next != null && q.val == q.next.val) {
                flag = true;
                q = q.next;
            }
            if(flag) {
                p.next = q.next; 
            }else {
                p = p.next;
            }          
            q = q.next;
        }
        return dummy.next;
    }
}

时间复杂度：O（N），N为链表长度
空间复杂度：O（1），指针消耗

另解：
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        // 可能会删除头结点
        ListNode dummy = new ListNode(-1, head);
        // 对下一个和下下个比较val
        ListNode cur = dummy;
        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 && cur.next.val == x) {
                    cur.next = cur.next.next;
                }               
            }else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

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

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

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

解：

:chestnut:解题思路：遍历

当头结点重复，可以删除第二个，这样头结点必不删除，不用设伪头结点
删除节点，cur指向上一个，cur.next 需判空再比较
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        while (cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

题：203. 移除链表元素

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

示例 1：
在这里插入图片描述

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

示例 2：

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

示例 3：

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

提示：

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

解：

解题思路：

头结点删除 => 加入伪头结点
删除元素 => 拿到上一个节点，while(cur.next)

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) return head;
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while(cur.next != null) {
            if(cur.next.val == val) {
                cur.next = cur.next.next; 
            }else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

时间复杂度：O（n）
空间复杂度：O（1）

题：1171. 从链表中删去总和值为零的连续节点

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

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

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

示例 2：

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

示例 3：

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

提示：

给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

解：

解题思路：前缀和

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        if(head == null) return head;
        // 头结点可能被删除 => 引入伪头结点
        ListNode dummy = new ListNode(0, head);  
        // HashMap记录前缀和，重复记录最后一次
        int sum = 0;
        HashMap<Integer, ListNode> map = new HashMap<>();
        for(ListNode i = dummy; i != null; i = i.next) {
            sum += i.val;
            map.put(sum, i);
        }
        // 二次遍历，删除前缀和相等的区间
        sum = 0;
        for(ListNode i = dummy; i != null; i = i.next) {
            sum += i.val;
            i.next = map.get(sum).next;
        }
        return dummy.next;
    }
}

时间复杂度：O（N），N为链表长度，遍历链表
空间复杂度：O（N），hashMap所占空间

2.2 链表结点索引

题：剑指 Offer 22. 链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

解：

解题思路：双指针

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return head;
        ListNode p = head, q = head;
        for(int i = 0; i < k; i ++) {
            p = p.next;
        }
        while(p != null) {
            p = p.next;
            q = q.next;
        }
        return q;
    }
}

时间复杂度：O（N），N为链表长度，p走了N步，q走了N - k
空间复杂度：O（1），双指针使用了额外的空间

题：面试题 02.02. 返回倒数第 k 个节点

题：876. 链表的中间结点

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

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

示例 1：

输入：[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.

示例 2：

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

提示：

给定链表的结点数介于 1 和 100 之间。

解：

解题思路：快慢指针

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = head, q = head;
        while(q != null && q.next != null) {
            p = p.next;
            q = q.next.next;
        }
        return p;
    }
}

时间复杂度：O（N），N为链表长度
空间复杂度：O（1），常数空间存放指针

题：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：

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

示例 2：

输入：[2,7,4,3,5]
输出：[7,0,5,5,0]

示例 3：

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

提示：

对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内

解：

解题思路：单增栈

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while(head != null) {
            list.add(head.val);
            head = head.next;
        }
        // 单增栈
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i ++) {
            while(!stack.isEmpty() && list.get(stack.peek()) < list.get(i)) {
                int index = stack.pop();
                res[index] = list.get(i);
            }
            stack.push(i);
        }
        return res;
    }
    
}

时间复杂度：O（N），遍历列表，链表
空间复杂度：O（N），栈、列表各占用N空间，N为链表长度

2.2 链表结点交换

题：24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：
在这里插入图片描述

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

示例 2：

输入：head = []
输出：[]

示例 3：

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

提示：

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

解：

解题思路：
递归步骤：

单个递归的核心步骤
递归间的连接点

在这里插入图片描述
AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        // 判空，或者一个
        if(head == null || head.next == null) return head;

        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;

        return next;
    }
}

时间复杂度：O（N），N为链表长度
空间复杂度：O（N），N为链表长度

另解：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        // 需要操作头
        ListNode dummy = new ListNode(0, head);
        ListNode temp = dummy;
        while(temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;
            node1.next = node2.next;
            node2.next = node1;
            temp = node1;
        }
        return dummy.next;
    }
}

题：1721. 交换链表中的节点

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

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

示例 1：
在这里插入图片描述

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

链表中节点的数目是 n
1 <= k <= n <= 105
0 <= Node.val <= 100

解：

解题思路：值交换

AC代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode left = dummy;      
        for(int i = 0; i < k; i ++) left = left.next;
        ListNode right = dummy; 
        ListNode cur = left;
        while(cur != null) {
            right = right.next;
            cur = cur.next;
        }
        int value = left.val;
        left.val = right.val;
        right.val = value;

        return head;
    }
}

时间复杂度：O（N）
空间复杂度：O（1）

解题思路：`节点交换

AC代码：

class Solution {
    public ListNode swapNodes(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;// 因为头结点可能会发生交换，所以要构造一个哑结点
        ListNode pre1 = dummy;// pre1指向第k个节点的前一个节点
        ListNode left = dummy.next;// 第k个节点
        ListNode pre2 = dummy;// pre2指向倒数第k个节点的前一个节点
        ListNode right = dummy.next;// 倒数第k个节点
        for(int i = 1; i < k; i++){
            pre1 = pre1.next;
            left = left.next;
        }
        ListNode cur = left;
        ListNode temp = left.next;// 第k个节点的后一个节点
        while(cur.next != null){
            pre2 = pre2.next;
            right = right.next;
            cur = cur.next;
        }
        if(right == pre1){// 特殊情况，倒数第k个节点在第k个节点的左侧
            right.next = temp;
            left.next = right;
            pre2.next = left;}
        else{
            left.next = right.next;
            if(pre2 == left){right.next = left;}// 特殊情况，第k个节点在倒数第k个节点的左侧
            else{
                pre2.next = left;
                right.next = temp;
            }
            pre1.next = right;
        }
        return dummy.next;
    }
}

二、双向链表

1.1 扁平化链表

题：430. 扁平化多级双向链表

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

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

示例 1：

输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
输出：[1,2,3,7,8,11,12,9,10,4,5,6]
解释：

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

在这里插入图片描述

扁平化后的链表如下图：

在这里插入图片描述

示例 2：

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

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

  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

如何表示测试用例中的多级链表？

以示例 1 为例：

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

序列化其中的每一级之后：

[1,2,3,4,5,6,null]
[7,8,9,10,null]
[11,12,null]

为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。

[1,2,3,4,5,6,null]
[null,null,7,8,9,10,null]
[null,11,12,null]

合并所有序列化结果，并去除末尾的 null 。

[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]

提示：

节点数目不超过 1000
1 <= Node.val <= 10^5

解：

解题思路：递归

AC代码：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        // 伪头结点
        Node dummy = new Node(0);
        dummy.next = head;
        
        while(head != null) {
            if(head.child == null){
                head = head.next;
            }else {
                Node temp = head.next; // 松手先保存

                // 递归
                Node dfsChild = flatten(head.child);
                head.next = dfsChild;
                head.child = null;
                dfsChild.prev = head;

                // head 移动到dfsChile末尾
                while(head.next != null) head = head.next;
                head.next = temp;
                if(temp != null) temp.prev = head;

                head = head.next;
            }
        };
        return dummy.next;
    }
}

时间复杂度：O（N ^2^）
空间复杂度：O（N）

解题思路：递归优化

由于我们递归处理head.child后不得不在找当前层的尾结点，导致算法时间度O（N ^2^）

可行性优化：额外设计一个dfs用于返回扁平化链表尾结点

AC代码：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;
};
*/

class Solution {
    public Node flatten(Node head) {
        dfs(head);
        return head;
    }
    Node dfs(Node head) {
        // 最后一个节点指针
        Node last = head;
        while(head != null) {
            if(head.child == null) {
                // 分别移动last、head指针
                last = head;
                head = head.next;              
            }else {
                // 松手先保存
                Node temp = head.next;
                Node childLast = dfs(head.child);
                head.next = head.child;
                head.child.prev = head;
                head.child = null;

                if(childLast != null) childLast.next = temp;
                if(temp != null) temp.prev = childLast;
                
                // 指针移动
                last = head;
                head = childLast;
            }
        }
        return last;
    }
}

时间复杂度：O（N）
空间复杂度：O（N）

三、循环链表

1.1 链表排序

题：剑指 Offer II 029. 排序的循环链表

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

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

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

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

示例 1：
在这里插入图片描述

输入：head = [3,4,1], insertVal = 2
输出：[3,4,1,2]
解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

在这里插入图片描述
示例 2：

输入：head = [], insertVal = 1
输出：[1]
解释：列表为空（给定的节点是 null），创建一个循环有序列表并返回这个节点。

示例 3：

输入：head = [1], insertVal = 0
输出：[1,0]

提示：

0 <= Number of Nodes <= 5 * 10^4
-10^6 <= Node.val <= 10^6
-10^6 <= insertVal <= 10^6

解：

解题思路：

画图分析:找到max(最后一个)，min
分两种情况 [min,max]区间内外
区间外：max.next = insertVal
区间内：移动min，min.next = insertVal

在这里插入图片描述

AC代码：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _next) {
        val = _val;
        next = _next;
    }
};
*/
class Solution {
    public Node insert(Node head, int insertVal) {
        // 判空
        if(head == null) {
            Node node = new Node(insertVal);
            node.next = node;
            return node;
        }
        // 寻找极大值、极小值
        Node max = head;
        Node min = head;
        Node cur = head.next; // 指针
        while(cur != head) {
            if(cur.val >= max.val) max = cur;
            if(cur.val <= min.val) min = cur;
            cur = cur.next;
        }
        // 分类讨论
        if(insertVal >= max.val || insertVal <= min.val) {
            // 最小的前面 == 最大的后面（循环链表）
            Node temp = new Node(insertVal, max.next);
            max.next = temp;
        }else {
            // 找到次小于insertVal的节点
            while(min.next.val < insertVal) min = min.next;
            Node temp = new Node(insertVal, min.next);
            min.next = temp;
        }
        return head;
    }
}

四、环形链表

1.1 快慢指针

题：剑指 Offer II 022. 链表中环的入口节点

解：

解题思路：

在这里插入图片描述

设v1，v2，s1，s2分别表示slow，fast的速度、路程，易得：
v2 = 2v1，s2 = 2s1，a，b见图
若相遇：fast 比 slow 多走了几个环
s2 = s1 + nb = 2s1 => s1 = nb
待求点的位置：a + nb = s1 + a => slow继续走a步
a步：双指针同步从head，fast、slow相遇点出发，相遇点即为待求点

AC代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 快慢指针
        ListNode fast = head, slow = head;
        // 相遇点
        while(true) {
            // 指针走到了链表末端
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

时间复杂度：O（N）
空间复杂度：O（1），双指针使用常数空间

题：142. 环形链表 II

题：面试题 02.08. 环路检测

题：141. 环形链表

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

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

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

示例 1：
在这里插入图片描述

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

示例 2：
在这里插入图片描述

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

示例 3：
在这里插入图片描述

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

提示：

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

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

解：

解题思路：同上

AC代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null) return false;
        ListNode slow = head, fast = head;
        while(true) {
            if(fast.next == null || fast.next.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
    }
}

时间复杂度：O（N）
空间复杂度：O（1）

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

你好，链表（^.^）

励志：

一、单向链表

1. 链表操作

1.1 链表旋转

题：61. 旋转链表

解：

题：25. K 个一组翻转链表

解：

1.2 链表相交

题：面试题 02.07. 链表相交

解：

题：剑指 Offer 52. 两个链表的第一个公共节点

题：160. 相交链表

题：剑指 Offer II 023. 两个链表的第一个重合节点

1.3 链表归并

题：21. 合并两个有序链表

解：

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

题：23. 合并K个升序链表

解：

题：剑指 Offer II 078. 合并排序链表

题：143. 重排链表

解：

1.4 链表排序

题：148. 排序链表

解：

题：剑指 Offer II 077. 链表排序

1.5 链表回文

题：234. 回文链表

解：

题：剑指 Offer II 027. 回文链表

题：面试题 02.06. 回文链表

1.6 链表逆序

题：剑指 Offer 06. 从尾到头打印链表

解：

题：剑指 Offer 24. 反转链表

解：

题：206. 反转链表

题：剑指 Offer II 024. 反转链表

题：445. 两数相加 II

解：

题：剑指 Offer II 025. 链表中的两数相加

题：92. 反转链表 II

解：

2. 链表结点操作

2.1 链表结点删除

题：剑指 Offer 18. 删除链表的节点

解：

题：237. 删除链表中的节点

解：

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

解：

题：剑指 Offer II 021. 删除链表的倒数第 n 个结点

题：237. 删除链表中的节点

题：82. 删除排序链表中的重复元素 II

解：

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

解：

题：203. 移除链表元素

解：

题：1171. 从链表中删去总和值为零的连续节点

解：

2.2 链表结点索引

题：剑指 Offer 22. 链表中倒数第k个节点

解：