链表

链表必须要掌握的题

• 反转单链表（递归 + 迭代）
• 反转链表指定区间
• 链表中每 K 个一组反转（hard）
• 寻找单链表的中点
• 合并两个排序的链表
• 合并 k 个已排序的链表 hard
• 判断链表是否有环（2014 百度考过）
• 判断链表环的入口
• 删除链表倒数第 N 个节点（2022 年，华润万家 全名 K 歌考过）
• 获取链表的倒数第 k 个节点：注意 head 仅一个元素，k=1 的情况
• 判断两个链表相交

链表基础

链表前序后序

void traverse(ListNode head) {
    // 前序位置
	traverse(head.next);
    // 后序位置
}

// 顺序打印链表
static void traverse(ListNode node) {
    if (node == null) return;
    // 前序
    System.out.print(node.val+" ");
    traverse(node.next);
}
// 1 2 3 4 5 6 7
// 倒序打印
static void traverse(ListNode node) {
    if (node == null) return;
    traverse(node.next);
    // 后序
    System.out.print(node.val+" ");
}
// 7 6 5 4 3 2 1

获取链表长度

private static int getLength(ListNode node) {
    ListNode cur = node;
    int len = 0;
    while (cur!=null) {
        cur = cur.next;
        len++;
    }
    return len;
}

获取链表第 N 个节点

1、获取链表中最后一个节点

// 获取链表最后一个节点：引入pre节点来记录最后一个节点
private static ListNode getLastNode(ListNode node) {
    ListNode cur = node;
    ListNode pre = null;
    while (cur != null) {
        pre = cur;
        cur = cur.next;
    }
    return pre;
}
// 获取链表最后一个节点：不引入其他节点
private static ListNode getLastNode(ListNode node) {
    ListNode cur = node;
    while (cur.next != null) {
        cur = cur.next;
    }
    return cur;
}

2、获取链表中最后一个节点前一个节点

private static ListNode getLastPreNode(ListNode node) {
    ListNode cur = node;
    ListNode pre = null;
    while (cur.next != null) {
        pre = cur;
        cur = cur.next;
    }
    return pre;
}

3、获取链表第 N 个节点 (n 从 0 或 1 开始)

// 不带哑元节点：i从1开始计数
private static ListNode getNNode(ListNode node, int n) {
    if (node == null) return null;
    ListNode cur = node;
    for (int i = 1; i < n; i++) {
        cur = cur.next;
    }
    return cur;
}
// 不带哑元节点：i从0开始遍历，遍历需要减去1次
private static ListNode getNNode(ListNode node, int n) {
    if (node == null) return null;
    ListNode cur = node;
    for (int i = 0; i < n - 1; i++) {
        cur = cur.next;
    }
    return cur;
}

// 带哑元节点且n从0开始，需多遍历1次：获取第n个节点
private static ListNode getNNode(ListNode node, int n) {
    if (node == null) return null;
    ListNode dummy = new ListNode(-1, node);
    ListNode cur = dummy;
    for (int i = 0; i < n; i++) {
        cur = cur.next;
    }
    return cur;
}

4、获取链表倒数第 N 个节点

public ListNode getKthFromEnd(ListNode head, int k) {
    ListNode right = head;
    for (int i = 0; i < k && right != null; i++) {
        right = right.next;
    }
    // 下面判断要去掉，防止head只有一个元素，k=1的情况，right直接=null返回了null，实际要返回一个元素
    // if (right == null) {
    //     return head;
    // }
    ListNode left = head;
    while (right != null) {
        right = right.next;
        left = left.next;
    }
    return left;
}
// 无有哑元节点：获取倒数第N个节点，i从0开始，都是i<k

操作链表时可用哑元 dummy 节点情况

1、生成新的链表

根据一个 List/数组生成一个新的链表，用哑元节点可避免需要处理 head==null 的情况

2、需要判断 head==null 的情况

1. 翻转链表：翻转链表涉及到 head==null 的情况
2. 合并链表
3. 删除倒数 N 个节点

链表面试题

反转链表相关

反转链表「汇总级别整理 🔥🔥🔥」

206. 反转链表 easy

题目：

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

递归解法

思路

1. 反转链表这个问题可以拆解成子问题，考虑用递归来解
2. 用递归就需要找到递推公式：fun(n) = fun(n-1)→1；递归结束条件 head==null 或 head.next==null
3. 我们 reverseList(head.next) 从第二个节点开始已经反转好，返回的是反转后的头节点
4. 接下来我们只需要将第一个节点反转过来，head.next 表示第二个节点: head.next.next = head
5. 要将 head 的指向 null，防止循环指向 1→2→1

递归图解





代码

public static ListNode reverseList(ListNode head) {
    // 判空
    if (head == null || head.next == null) return head;

    // 第二个节点及以后的节点都反转了，返回的node是反转后的头节点
    ListNode node = reverseList(head.next);
    // 现在反转第一个节点 head.next代表第二个节点，将第二个节点指向第一个节点
    head.next.next = head;
    head.next = null; // 防止循环指向 1→2→1
    return node;
}

复杂度

• 时间复杂度：O(n)，链表需要遍历 n 次，需要对每个链表反转 1 次
• 空间复杂度：O(n)，遍历 1 次一个栈，需要遍历 n 次，调用栈为 n 层

迭代方式 (推荐)

思路

1. 每遍历一个节点，就将当前节点给反转过来
2. 需要 2 个临时变量，pre 记录当前前一个节点，用于反转当前节点时用，pre 默认指向 null；cur 记录当前节点，cur 默认指向 head
3. 遍历结束条件 cur==null
   1. pre 默认指向 null，cur 默认指向 head；每反转一个节点后，pre 和 cur 同步向前走一步
   2. 需要记录 cur.next 用来作为下一个节点反转用：next=cur.next
   3. 反转当前节点 cur：cur.next = pre
   4. pre 指向当前节点（pre 往前走一步）：pre=cur
   5. cur 指向下一个节点（cur 往前走一步）：cur=next （如果最开始不记录 cur.next，这里就丢失了）
   6. 最后 cur 指向到 null 遍历结束，pre 指向最后一个节点
   7. 返回 pre 即可

代码

public static ListNode reverseList(ListNode head) {
    // 判空
    if (head == null || head.next == null) return head;

    ListNode pre = null; // 指向前一个节点
    ListNode cur = head; // 指向当前遍历的节点
    while (cur != null) { // 遍历逐个节点反转
        // 记录当前节点的下一个节点备用，否则当前节点反转后找不到了
        ListNode next = cur.next;
        // 反转当前节点，当前节点指向pre
        cur.next = pre;
        // pre记录当前节点，用于下一轮节点反转
        pre = cur;
        // 当前节点往下走
        cur = next;
    }
    return pre; // 到这里cur为null，指向最后一个元素的下一个元素即为null了
}

复杂度

• 时间复杂度：O(n)，链表需要遍历 n 次
• 空间复杂度：O(1)

反转链表前 N 个元素

二趟遍历

思路

1. 定义哑元节点，就不需要处理边界问题了
2. 先遍历 n 次，找到第 n 个节点
3. 临时存储首节点 (即 left 节点)，节点下一个节点（用于反转后指向）
4. 断开 n 节点的指向，即 node.next = null

代码

public static ListNode reverseListN(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head);

    // 找到第n个节点
    ListNode nNode = dummy;
    for (int i = 0; i < n && nNode != null; i++) {
        nNode = nNode.next;
    }
    if (nNode == null) {
        return head;
    }
    System.out.println("找到第" + n + "个节点，node=" + nNode);

    // 临时记录节点
    ListNode left = dummy.next;
    ListNode rightAfter = nNode.next;
    // 断开连接
    nNode.next = null;

    // 反转前n个节点
    ListNode pre = null;
    ListNode cur = dummy.next;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    // 此时pre为头节点
    left.next = rightAfter;
    return pre;
}

一趟遍历

思路

1. 不需要先遍历出第 n 个节点，我们只需要边遍历的过程中边反转，遍历一个节点反转一个
2. 也需要引入哑元节点
3. 记录 left 节点，便于反转后 left 需要指向 n 节点的下一个
4. 遍历 n 次，反转链表
5. 反转后将链表的首尾链接起来

代码

public static ListNode reverseListN(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head);

    ListNode left = dummy.next;

    ListNode pre = null;
    ListNode cur = dummy.next;
    // 边遍历边反转
    for (int i = 0; i < n && cur != null; i++) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    System.out.println("pre=" + pre + ",cur=" + cur);
    // pre为新的头节点, cur为n个节点的下一个节点
    dummy.next = pre;
    left.next = cur;
    return dummy.next;
}

92. 反转链表 II (反转指定区间链表) 需要哑元节点处理边界 medium

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 输入： head = [1,2,3,4,5], left = 2, right = 4 输出： [1,4,3,2,5]

解法 1：遍历

思路

1. 添加哑元节点来处理边界问题，left=1 时不加哑元节点，边界很难处理
2. 先找到 left 节点前一个节点 leftNodePre（用于反转后指向新的反转链表头）；保存 left 节点（用于反转后指向 right 下一个节点）
3. 遍历 left 到 right，不停地反转链表
4. 区间反转完成后，leftNodePre.next 指向 pre（pre 为反转后头节点）；left 指向 cur（cur 此时为 right 节点的下一个节点）

代码

public static ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null || left == right) return head;

    // 哑元节点，不然left=1的情况很难处理
    ListNode dummyNode = new ListNode(-1, head);
    // 先找到第left节点的前一个节点
    ListNode leftNodePre = dummyNode;
    for (int i = 0; i < left - 1 && leftNodePre != null; i++) {
        leftNodePre = leftNodePre.next;
    }
    if (leftNodePre == null) {
        System.out.println("left=" + left + ",right=" + right + "，leftNodePre为null");
        return head;
    }
    System.out.println("找到第" + left + "个节点=" + leftNodePre);
    ListNode leftNode = leftNodePre.next; // 第left索引处的节点，用于反转后的指向
    // 遍历反转区间的链表
    ListNode pre = leftNodePre;
    ListNode cur = leftNode;
    for (int i = left; i <= right; i++) {
        System.out.println("----- left=" + left + ",right=" + right + ",i=" + i + ",cur=" + cur);
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    // pre为反转后的头节点，右leftNodePre指向它
    leftNodePre.next = pre;
    // leftNode反转后到右边了，其next指向cur
    leftNode.next = cur;
    return dummyNode.next;
}

解法 2：还是遍历

思路

1. 和解法 1 类似
2. 先找到 left 的前一个节点并记录，再找到 right 节点并记录
3. 临时记录 left 索引处节点，right 下一个节点（用于反转后连接），并删除区间前后节点的指向
4. 反转链表指定的区间
5. 将反转后的链表重新链起来

代码

public static ListNode reverseBetween(ListNode head, int left, int right) {
    // 边界判断
    if (head == null || head.next == null) return head;
    // 添加哑元节点，更好的处理边界
    ListNode dummyNode = new ListNode(-1, head);

    // 先找到left前一个节点
    ListNode leftPre = dummyNode;
    for (int i = 0; i < left - 1 && leftPre != null; i++) { // 如果没有dummyNode，到left-1
        leftPre = leftPre.next;
    }
    if (leftPre == null) return null;
    System.out.println("left=" + left + ", left前一个=" + leftPre);
    // 找到right节点(从leftPre开始找，避免从头开始找)
    ListNode rightNode = leftPre;
    for (int i = 0; i < right - left + 1; i++) {
        rightNode = rightNode.next;
    }
    if (rightNode == null) return null;
    System.out.println("right=" + right + ", right节点=" + rightNode);

    // 记录left节点
    ListNode leftNode = leftPre.next;
    ListNode rightAfterNode = rightNode.next;

    // 断开区间[left,right]节点
    leftPre.next = null; // 要断开连接，不然反转会2→1了
    rightNode.next = null;

    // 反转链表
    ListNode pre = leftPre;
    ListNode cur = leftNode;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    // 再将区间[2,4]重新连接
    leftPre.next = pre; // 此时pre为反转后的头节点
    leftNode.next = rightAfterNode;

    System.out.println("right=" + right + ", right后一个=" + rightNode);
    return dummyNode.next;
}

解法 3：递归

思路

1. 先找到 m 节点的前一个节点，n 节点的后一个节点，用于反转链表后连接；引入哑元节点，来处理 m=1 边界情况
2. 找到 m 的前一个节点和 n 节点后一个节点后，将 [m, n] 区间和其他节点断开
3. 现在 [m, n] 是一个全新的节点，直接反转
4. 反转后再将节点连接起来
5. 注意：引入哑元节点后，要找到 m 的前一节点 preNode，遍历从 0 到 left-1；要找到 n 节点，需要从 preNode 节点遍历 right-left+1 次

public static ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null) return head;

    // 引入哑元节点，方便处理边界问题
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    // 1、先找到left位置的前一个，right的后一个，方便反转后链接起来
    ListNode preNode = dummy;
    for (int i = 0; i < left - 1 && preNode != null; i++) {
        preNode = preNode.next;
    }
    System.out.println("找到preNode=" + (preNode == null ? "null" : preNode) + "，left=" + left + "，right=" + right);
    if (preNode == null) {
        return head;
    }
    ListNode rightNode = preNode;
    for (int i = 0; i < right - left + 1 && rightNode != null; i++) {
        rightNode = rightNode.next;
    }
    System.out.println("找到rightNode=" + (rightNode == null ? "null" : rightNode.val) + "，left=" + left + "，right=" + right);
    if (rightNode == null) {
        return head;
    }

    ListNode endNode = rightNode.next;
    System.out.println("endNode=" + endNode);
    ListNode leftNode = preNode.next;
    System.out.println("leftNode=" + leftNode);

    // 断开连接
    preNode.next = null;
    rightNode.next = null;

    System.out.println("开始翻转链表leftNode=" + leftNode);
    ListNode newHead = reverse(leftNode);
    System.out.println("反转链表后newHead=" + newHead + ", preNode=" + preNode + "， leftNode=" + leftNode);
    preNode.next = newHead;
    leftNode.next = endNode;
    return dummy.next;
}

public static ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode last = reverse(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

两两链表反转

可以看作 K 个一组翻转链表 K=2 的情况

25. K 个一组翻转链表（hard 得掌握）

题目

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

1、一个辅助栈

思路

1. 辅助栈 stack，用来临时存储获取到的节点
2. 遍历链表，每当 stack 中元素等于 k 时，就将 stack 中数据取出来，重新生成新的链表（由于栈的后进先出就可以实现翻转的功能）
3. 链表遍历结束后，当 stack 还有元素时，这里面的节点是不需要翻转的，直接找到栈底节点，添加到新生成的链表最后面即可
4. 由于需要处理新的节点是否首次为 null 问题，所以我们可以引入哑元节点，简化这种边界处理

代码

public static ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null || k <= 1) return head;
    // 辅助栈：每次达到k个节点时，将其出栈，重新生成新的链表
    Stack<ListNode> stack = new Stack<>();
    ListNode temp = head;

    ListNode dummyNode = new ListNode(-1, null);
    ListNode cur = dummyNode;

    while (temp != null) {
        stack.push(temp);
        temp = temp.next;
        if (stack.size() == k) {
            while (!stack.isEmpty()) {
                ListNode node = stack.pop();
                node.next = null; // 断开连接，防止指向循环
                // 出栈
                cur.next = node;
                cur = node;
            }
        }
    }
    // 还剩下最后几个不足k个，不需要反转，取最后一个元素即可
    ListNode end = null;
    while (!stack.isEmpty()) {
        end = stack.pop();
    }
    cur.next = end;
    return dummyNode.next;
}

复杂度

• 时间复杂度 O(n) 需要遍历整个链表
• 空间复杂度 O(n) 需要个临时辅助栈

2、迭代

图解k个一组翻转链表
思路

1. k 个一组翻转链表，需要解决 k 个一组链表翻转后链表的连接问题；一般会引入哑元节点更好地处理边界问题
2. 每 k 个一组进行翻转，翻转后处理好链表的前后连接问题
3. 翻转前准备
   1. pre：每组中链表头节点的前驱节点，用于将前组和后续一组连接起来
   2. end：每组中最后一个节点，用于翻转后和后续链表顺利连接来；每组开始翻转前都需要遍历 k 次找到该组最后一个节点，如果不足 k，出现 end=null，说明到了最后一组直接 return
   3. start：记录每组翻转前的头节点，用于和下一组连接起来
   4. next：临时记录下一组的头结点，防止翻转后找不到下一组的头节点了；在 next=end.next 后，end.next 继续断开连接，否则局部翻转就会有问题 (翻转了整个链表，导致 leetcode 超时)
4. 一组翻转（同翻转整个链表，头结点为 start）
5. 一组翻转后
   1. 一组翻转后，需要将链表重新连接起来；
   2. 头节点连接：pre.next = reverseNode(start)
   3. 尾节点连接 (start 经过翻转后变成了尾结点)：start.next = next
6. 准备下一组
   1. pre = start，作为下一组头节点的前驱
   2. end = pre，end 默认和 pre 保持一致，在每组翻转前会遍历 k 次指向该组的最后一个节点
7. 直到 end.next==null，即链表到达最后了，翻转结束

代码

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummyNode = new ListNode(0);
    dummyNode.next = head;

    // pre记录每k个一组中起始节点的前驱节点
    ListNode pre = dummyNode;
    // end记录每k个一组中最后的节点
    ListNode end = dummyNode;

    // 当end.next==null时，也就结束了
    while (end.next != null) {
        // 先确定该组的最后一个节点，用end记录
        for (int i = 0; i < k && end != null; i++) {
            end = end.next;
        }
        // end==null说明到了最后一组且不足k个了，直接break
        if (end == null) {
            break;
        }
        // 记录该组翻转起始点
        ListNode start = pre.next;
        // 记录下一组的起始点，避免翻转后链表找不到
        ListNode next = end.next;
        // 断开连接(如果不断开连接leetcode就会超时)
        end.next = null;

        // 现在开始翻转
        // 翻转完成了，头节点为end，尾节点为start
        // 重新连接到链表中去
        pre.next = reverseNode(start);
        start.next = next; // start此时为该组最后一个节点

        // 继续下一组
        // pre指向下一组的前驱节点，也就是翻转后为start
        pre = start;
        // end默认也是指向下一组的前驱节点
        end = pre;
    }
    return dummyNode.next;
}

public static ListNode reverseNode(ListNode head) {
    // 迭代法翻转链表
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

复杂度

• 时间复杂度 O(n*k)，最坏是 k=n，O(n^2)
• 空间复杂度 O(1)

3、递归（翻转链表断开连接解法）

题解1：【忍者算法】全网最清晰易懂的题解
思路

1. 递归法关键是要找到递归公式和递归结束条件
   1. 公式：reverseKGroup(head(第 1 组头节点), k) = f(head(第二组头节点), k)
   2. 结束条件：head==null || head.next ==null 返回 head; 不足 k 个时返回 head
2. 递归
   1. 找到第 1 组中第 k 节点，firstTail
   2. 记录下一组头节点 nextHead=firstTail.next；断开第 1 组和后面的连接 firstTail.next=null
   3. 反转第 1 组，此时 firstTail 为反转后头节点，head 为尾节点
   4. 递归调用下一组 reverseKGroup(nextHead, k)；
   5. 将第 1 组和后面组的结果连接起来：head.next = reverseKGroup(nextHead, k)
   6. 返回 firstTail 即可

图解思路

代码

public static ListNode reverseKGroup3(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    // 找到要该组中的首尾节点
    ListNode firstTail = head;
    for (int i = 0; i < k - 1; i++) {
        if (firstTail == null) {
            return head;
        }
        firstTail = firstTail.next;
    }
    // 下一组的节点
    ListNode nextHead = firstTail.next;
    // 断开连接，翻转
    firstTail.next = null;

    // 翻转链表
    reverseNode(head);
    // 翻转后，firstTail变成头节点了，firstHead变成尾节点了

    // 递归翻转下一组的节点
    head.next = reverseKGroup3(nextHead, k);
    return firstTail;
}
public static ListNode reverseNode(ListNode head) {
    // 迭代法翻转链表
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

4、递归（翻转链表不断开连接）

题解2：递归java
思路

1. 先找到第 k 个节点的下一个 tail（这里的 tail 是下一个 k 组的头节点，也可以是第 k 个节点，代码写法大同小异）
2. 先翻转前 k 个元素
   1. 左开右闭，tail 需要是第 k 个节点的下一个节点 reverseNode(ListNode head, ListNode tail)
   2. 返回值为翻转后的头节点
3. 将翻转后链表头连接起来
   1. newHead = reverseNode(head, tail)
   2. head.next = newHead
4. 返回 newHead

思路图解

代码

public static ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    ListNode tail = head; // tail是找到当前组的下一个节点
    for (int i = 0; i < k; i++) {
        if (tail == null) { // 剩余数量小于k的话，则不需要反转。
            return head;
        }
        tail = tail.next;
    }
    // 反转前 k 个元素
    ListNode newHead = reverseNode(head, tail);
    // 递归调用：tail就是下一组链表的头节点
    head.next = reverseKGroup(tail, k);
    return newHead;
}
// 翻转head到tail的链表 注意：翻转为左闭又开区间，所以本轮操作的尾结点其实就是下一轮操作的头结点
public static ListNode reverseNode(ListNode head, ListNode tail) {
    // 迭代法翻转链表
    ListNode pre = null;
    ListNode cur = head;
    while (cur != tail) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

// 或者更好的理解版本
public static ListNode reverseKGroup2(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    ListNode tail = head;
    for (int i = 0; i < k - 1 && tail!=null; i++) {
        tail = tail.next;
    }
    if (tail == null) { // 剩余数量小于k的话，则不需要反转。
        return head;
    }
    ListNode next = tail.next;
    // 反转前 k 个元素
    reverseNode(head, next);
    // 递归调用：tail就是下一组链表的头节点
    head.next = reverseKGroup2(next, k);
    return tail;
}

链表合并

21. 合并两个有序链表 easy

题目

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

解法 1：双指针 + 哑元节点 + 额外的链表 最优解

思路

1. 双指针，list1 和 list2；临时的链表 pre；引入哑元节点（dummyNode 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性，如 head==null 的情况）
2. 遍历链表，每次比对 list1 和 list2，如果 list1 的值小于等于 list2，那么 pre 的 next 指向 list1，list1 指针往前一步，否则 pre 指向 list2，list2 指针往前一步；pre 指针也往前一步
3. 遍历结束条件是 list1 且 lsit2 不为 null
4. 最后还需要判断是否还存在 list1 或 list2 不为 null 的情况，说明还有未被添加的链表，直接添加在 pre 最后面
5. 最后返回 dummyNode.next

代码

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummyNode = new ListNode(0);
    ListNode pre = dummyNode;
    while (list1 != null && list2 != null) {
        // 将值较小的的节点接到pre指针
        if (list1.val <= list2.val) {
            pre.next = list1;
            list1 = list1.next;
        } else {
            pre.next = list2;
            list2 = list2.next;
        }
        // pre 指针不断前进
        pre = pre.next;
    }
    // left还有元素，全局追加在后面
    if (list1 != null) {
        pre.next = list1;
    }
    // right还有元素，全局追加在后面
    if (list2 != null) {
        pre.next = list2;
    }
    return dummyNode.next;
}

复杂度

• 时间复杂度：O(n)，最差需要遍历整个链表 n
• 空间复杂度：O(n)，额外的链表空间

解法 2：递归

思路

代码

public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    if (list1.val <= list2.val) { // list1的值不大于list2的值，合并list1[0]和mergeTwoLists2的结果
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeTwoLists1(list1, list2.next);
        return list2;
    }
}

复杂度

• 时间复杂度：O(m+n) m 和 n 为 list1 和 list2 的长度
• 空间复杂度：O(m+n) 需要调用 mergeTwoLists m+n 次

**23. 合并K个升序链表 **（得掌握 hard）

https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
题目

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。 输入： 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、辅助 List+ 排序

思路

1. 临时辅助 List，用于将所有的链表临时保存起来
2. 对 List 中的节点进行升序排序
3. 将 List 中的元素重新生成一个链表

代码

public static ListNode mergeKLists(ListNode[] lists) {
    // 临时List保存链表中所有节点
    List<ListNode> list = new ArrayList<>();
    for (ListNode node : lists) {
        while (node != null) {
            list.add(node);
            node = node.next;
        }
    }
    // List元素排序
    list.sort(Comparator.comparingInt(l -> l.val));
    // List元素生成新的链表
    ListNode dummyNode = new ListNode(0);
    ListNode pre = dummyNode;
    for (ListNode n : list) {
        pre.next = n;
        pre = pre.next;
    }
    return dummyNode.next;
}

复杂度

• 时间复杂度：O(n)+O(nlogn)+O(n) n 表示列表中所有链表的结点数量，首先遍历所有结点 O(N)，排序 O(NlogN)，生成新的链表 O(n)
• 空间复杂度：O(n)，额外的 List

2、优先队列 PriorityQueue（堆排序）

思路

1. 将所有的节点按升序都添加到优先队列中去（小根堆，堆顶存放最小值）
2. 遍历队列，不断的取堆顶的节点，然后重新生成新的链表

代码

public static ListNode mergeKLists1(ListNode[] lists) {
    // 优先级队列，最小堆
    PriorityQueue<ListNode> queue = new PriorityQueue<>(
        lists.length, (a, b)->(a.val - b.val));
    for (ListNode node : lists) {
        while (node != null) {
            ListNode next = node.next;
            node.next = null; // 要断开连接，否则报循环引用 Error - Found cycle in the ListNode
            queue.add(node);
            node = next;
        }
    }
    System.out.println("queue中的元素=" + queue);
    // List元素生成新的链表
    ListNode dummyNode = new ListNode(0);
    ListNode pre = dummyNode;
    while (!queue.isEmpty()) {
        pre.next = queue.poll();
        pre = pre.next;
    }
    return dummyNode.next;
}

复杂度

• 时间复杂度 O(Nlogk)：N 表示列表中所有链表的结点数量，k 表示链表的数量，优先队列中的元素不超过 k 个，那么插入和删除的时间代价为 O(logk)，这里最多有 N 个点，对于每个点都被插入删除各一次，故总的时间代价即渐进时间复杂度为 O(Nlogk)
• 空间复杂度 O(k)：优先队列中的元素不超过 k 个，故渐进空间复杂度为 O(k)

3、类归并排序，分治法（最优解）

思路

1. 分治就是不断缩小其规模，再不断合并扩大的过程
2. 划分：首先将所有的链表数组划分：8 分 4、4 分 2、2 分 1，只有 1 个元素时，认为是有序了
   1. 每次取中间，将数组一分为二
   2. 当划分到不能划分时，只有 1 个元素时，直接返回该元素
3. 合并：
   1. 2 个元素两两合并成有序

思路图解

代码

public static ListNode mergeKLists(ListNode[] lists) {
    return divider(lists, 0, lists.length - 1);
}
// 分
// 通过mid将数组一分为二，并不断缩小规模，当规模为1时返回并开始合并
// 通过合并两个链表，不断增大其规模，整体看就是不断缩小-最后不断扩大的过程
public static ListNode divider(ListNode[] lists, int start, int end) {
    // 边界
    if (start > end) return null;
    // 只有1个元素时，认为已经有序
    if (start == end) return lists[start];

    // 中心点
    int mid = start + (end - start) / 2;

    // 分，不定义遍历更省空间
    //        ListNode left = divider(lists, start, mid);
    //        ListNode right = divider(lists, mid + 1, end);

    // 治
    return merge(divider(lists, start, mid), divider(lists, mid + 1, end));
}
// 治 合并两个有序链表
public static ListNode merge(ListNode list1, ListNode list2) {
    ListNode dummyNode = new ListNode(0);
    ListNode pre = dummyNode;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            pre.next = list1;
            list1 = list1.next;
        } else {
            pre.next = list2;
            list2 = list2.next;
        }
        pre = pre.next;
    }
    if (list1 == null) pre.next = list2;
    if (list2 == null) pre.next = list1;
    return dummyNode.next;
}

复杂度

• 时间复杂度：O(log2n) 其中 n 为所有链表的总节点数，分治为二叉树型递归，最坏情况下二叉树每层合并都是 O(n) 个节点，因为分治一共有 O(logn) 层
• 空间复杂度：O(log2n)，最坏情况下递归 log2nk 层，需要 log2n 的递归栈

链表环问题

141. 环形链表(链表否有环) easy

题目

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

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

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

解法 1：哈希表法

思路

1. 借助 HashSet 不能存重复节点的特性
2. 每次遍历链表时将节点添加到 hashset 中去
   1. 如果添加成功表示没有环
   2. 如果添加失败了表示有环，该节点就是环的入口
3. 否则没有环

public static boolean hasCycle1(ListNode head) {
    // 边界
    if (head == null || head.next == null) return false;
    HashSet<ListNode> set = new HashSet<>();
    while (head != null) {
        if (!set.add(head)) {
            System.out.println("有环，环节点=" + head.val);
            return true;
        }
        head = head.next;
    }
    return false;
    }
}

解法 2：快慢指针（fast 比 slow 快 2 步）

思路

1. 采用快慢指针法，fast 表示快指针，slow 表示慢指针
2. 每当慢指针 slow 前进一步，快指针 fast 就前进两步
3. 如果 fast 最终遇到空指针，说明链表中没有环；如果 fast 最终和 slow 相遇，那肯定是 fast 超过了 slow 一圈，说明链表中含有环。

若有环，两指针一定会相遇。因为每走 1 轮，fast 与 slow 的间距 +1，fast 终会追上 slow；

public static boolean hasCycle(ListNode head) {
    // fast比slow快2步
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) { 
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

142. 环形链表 II(链表有环的入口) medium

解法 1：哈希表法

思路

1. 遍历链表，将元素添加到 HashSet 中
2. 添加成功则继续走；如果添加失败了，说明出现了环，此时该节点就是环的入口

代码

public ListNode EntryNodeOfLoop3(ListNode pHead) {
    HashSet<ListNode> set = new HashSet<>();
    while (pHead != null) {
        if (!set.add(pHead)) { // false，为添加成功，那就是已经存在了节点，出现了环
            return pHead;
        }
        pHead = pHead.next;
    }
    return null;
}

解法 2：快慢指针 + 临时 temp 法 最优解

思路

1. 判断链表是否有环，有环才继续下一步
2. 当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

原理
假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步

fast 一定比 slow 多走了 k 步，这多走的 k 步其实就是 fast 指针在环里转圈圈，所以 k 的值就是环长度的「整数倍」。
假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。
巧的是，如果从相遇点继续前进 k - m 步，也恰好到达环起点。因为结合上图的 fast 指针，从相遇点开始走 k 步可以转回到相遇点，那走 k - m 步肯定就走到环起点了：

代码

public ListNode detectCycle(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    // 1. 快慢指针找到是否有环
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (slow == fast) { // 有环
            // 2. 找到环了，用新的临时指针从head开始，和slow一起走，每次走一步，相遇点就是环的入口
            fast = head;
            while (fast != slow) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }
    return null;
}

链表删除问题

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

题目

给你一个链表，删除链表的倒数第 n_ _ 个结点，并且返回链表的头结点。 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

解法 1：计算链表长度 + 哑元节点删除

思路

1. 添加哑元节点 dummyNode，解决各种判空的情况
2. 先计算链表的长度 len，注意 n>len 的情况
3. 遍历链表到 len-n，找到倒数第 n 个节点 (n 从 0 开始的话为 len-n-1，从 1 开始的话就是 len-n)
4. 找到倒数第 n 个节点的前一个节点，删除节点

// 计算链表长度，哑元节点
public static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummyNode = new ListNode(-1, head);
    // 首先计算链表的长度
    int len = getLength(dummyNode.next);
    System.out.println("链表长度 len=" + len + ", n=" + n);

    // n超过len，返回null
    if (n > len) {
        return null;
    }

    // 再遍历链表，找到倒数第n个节点的前一个节点：len-n位置的节点刚好是倒数第n个节点
    ListNode pre = dummyNode; // 由于采用了dummyNode需要加个1，为len - n - 1；不用dummyNode的话，pre可能为空（当链表只有1个节点时）
    for (int i = 0; i < len - n; i++) {
        pre = pre.next;
    }
    System.out.println("链表倒数第" + n + "个节点的前1个节点=" + pre);

    // 删除节点，如果没有哑元节点，在只有一个节点时pre.next会为空，泡NPE
    pre.next = pre.next.next; // pre.next要判空吗？(全名K歌问的)
    return dummyNode.next;
}

复杂度
时间复杂度：O(n)+O(len-n)，多了遍历全链表的次数
空间复杂度：O(1)

解法 2：快慢指针法

思路

1. 添加哑元节点 dummyNode 指向 head 前面 (引入哑元节点的目的是为了防止 n 长度等于链表长度时导致的 fast 为 null)
2. 利用快慢指针法，slow 慢指针，fast 快指针; 最开始 slow 和 fast 都指向 dummyNode
3. 先让 fast 先走 n 步，那么 fast 和 slow 就差了 n 步；这时需要判断 fast 是否为 null（fast 遍历过程中和 n 步走完都需要判断）
4. 当 fast==null 时，slow 停留在倒数第 n 个节点上；由于删除节点要找到前一个节点，所以判断条件为 fast.next!=null
5. 此时倒数第 n 个节点的前一个节点为 slow，删除下一个节点即可

代码 1

public static ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null) return null;
    ListNode dummyNode = new ListNode(-1, head);
    // 定义快慢指针
    ListNode fast = dummyNode;
    // 快指针先跑n步
    for (int i = 0; i < n && fast != null; i++) {
        fast = fast.next;
    }
    System.out.println("fast跑了" + n + "步，fast=" + fast);
    if (fast == null) { // fast为null，说明n大于链表长度了
        return null;
    }
    ListNode slow = dummyNode;
    // slow和fast一起跑，fast=null时，slow指向倒数第n个节点，要删除的话需要找到其前一个节点
    while (fast.next != null) { // 如果是fast!=null，只是找到倒数第n个节点
        fast = fast.next;
        slow = slow.next;
    }
    System.out.println("slow=" + slow);
    slow.next = slow.next.next; // slow.next不会为null吗（全名k歌），不需要前面fast判断了
    return dummyNode.next;
}

代码 2：最优解

先找倒数第 n 个前节点，删除

public ListNode removeNthFromEnd(ListNode head, int n) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    // 删除倒数第 n 个，要先找倒数第 n + 1 个节点
    ListNode x = findFromEnd(dummy, n + 1);
    // 删掉倒数第 n 个节点
    x.next = x.next.next;
    return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
    ListNode p1 = head;
    // p1 先走 k 步
    for (int i = 0; i < k; i++) {
        p1 = p1.next;
    }
    ListNode p2 = head;
    // p1 和 p2 同时走 n - k 步
    while (p1 != null) {
        p2 = p2.next;
        p1 = p1.next;
    }
    // p2 现在指向第 n - k + 1 个节点，即倒数第 k 个节点
    return p2;
}

复杂度
时间复杂度：O(n)
空间复杂度：O(1)

注意

1. 引入哑元节点，是为了防止 n 等于链表长度，如果 slow 和 fast 都指向 head，跑了 n 步后，fast 指向 null 了
2. 跑 n 步从 0 开始计算的
3. fast 先跑 n 步后， slow 和 fast 一起跑，当 fast 为 null 时，slow 处于倒数第 n 个位置，如果要删除的话，需要找到前一个节点，所以改成判断条件 fast.next!=null 即可找到要删除的倒数第 n 个节点的前一个节点，然后删除倒数第 n 个节点即可

83. 删除排序链表中的重复元素（删除重复，保留一个重复元素）

题目

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

图解

代码 1：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;
    ListNode slow = head, fast = head;
    while (fast != null) {
        if (fast.val != slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
}

代码 2：遇到重复的节点就删除

1. 指定 cur 指针指向头部 head
2. cur.next!=null 为循环条件
3. 当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，这样就能达到去重复的效果
4. 如果不相等则 cur 移动到下一个位置继续循环

public ListNode deleteDuplicates(ListNode head) {
    if (head == 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;
}

删除有序链表中重复元素 - 重复元素一个也不保留

public ListNode deleteDuplicates2(ListNode head) {
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = head;

    ListNode pre = dummyNode; // 前一个节点
    ListNode cur = dummyNode.next;

    while (cur != null && cur.next != null) { // 遍历到最后一个元素
        if (cur.val == cur.next.val) { // 存在相同的节点
            // 继续找到下一个不相同的节点
            while (cur.next != null && cur.val == cur.next.val) {
                cur = cur.next;
            }
            pre.next = cur.next; // 断开相同节点的
        } else {// 存在不相同的节点
            pre = cur;
        }
        cur = cur.next;
    }
    System.out.println("遍历后，pre=" + pre + ", cur=" + cur);
    return dummyNode.next;
}

获取链表节点

获取链表中倒数最后k个结点

BM8 链表中倒数最后k个结点
题目

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第 k 个节点。 如果该链表长度小于 k，请返回一个长度为 0 的链表。 要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(1)，时间复杂度 O(n) 输入:{1,2,3,4,5},2 返回值:{4,5} 说明：返回倒数第 2 个节点 4，系统会打印后面所有的节点来比较。

解法 1：计算链表长度 length，循环到 length-k，就获取到了

计算链表长度 length，循环到 length-k，就获取到了

解法 2：快慢指针

left 和 right 都指向 head，right 先走 k 步；然后 left 和 right 不停地往前走，直到 right 为 null，left 即为倒数 k 节点

代码：
注意：head 只有一个元素，k=1 的情况

public ListNode getKthFromEnd(ListNode head, int k) {
    // 双指针
    ListNode fast = head;
    for (int i = 0; i < k && fast != null; i++) {
        fast = fast.next;
    }
    // 不能加上这个，加了这个head只有一个元素，k=1时，返回的是null
    // if (right == null) {
    //     return head;
    // }
    ListNode slow = head;
    // 快慢一起跑
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为链表的长度。需要两次遍历。
• 空间复杂度：O(1)

876. 链表的中间结点

题目

给定一个头结点为 head 的非空单链表，返回链表的中间结点。 如果有两个中间结点，则返回第二个中间结点。

解法 1：快慢指针 不能用 dummy

思路

1. 让两个指针 slow 和 fast 分别指向链表头结点 head
2. 每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点
3. 如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。
4. 不能用 dummy，用了 dummy 的话，如果链表长度是偶数，返回的是两个中间节点靠前的节点，就不符合题目要求了

代码

public static ListNode middleNode(ListNode head) {
    // 不能用dummy，用了dummy的话，如果是偶数就会返回中间2个节点的前一个
//        ListNode dummy = new ListNode(0);
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

// 当链表长度为偶数时，上面是中点是链表中心靠后的
// 添加哑元节点，可实现链表中心靠前
static ListNode middle1(ListNode node) {
    ListNode dummy = new ListNode(0);
    dummy.next = node;
    ListNode slow = dummy;
    ListNode fast = dummy;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

其他链表题

160. 相交链表(两个链表的第一个公共结点)

牛客网：两个链表的第一个公共结点
题目

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

解法 1：哈希表

思路

1. 用一个 HashSet，先把 pHead1 的所有节点都存储进去
2. 再遍历 pHead2，如果存在 add 不进去的节点，那么这就是相交的节点；否则就是不存在相交

代码

public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2) {
    HashSet<ListNode> set = new HashSet<>();
    // 将pHead1全部存到set
    while (pHead1 != null) {
        set.add(pHead1);
        pHead1 = pHead1.next;
    }
    // 遍历pHead2，添加到set，如果存在相同元素，那么就是公共部分；否则不存在公共部分
    while (pHead2 != null) {
        if (!set.add(pHead2)) { // false表示已经存在相同元素
            return pHead2;
        }
        pHead2 = pHead2.next;
    }
    return null;
}

复杂度分析

• 时间复杂度 O(m+n) m 和 n 为两条链表长度，最差最后一个元素相交
• 空间复杂度 O(m+n-1) m 和 n 为两条链表长度，最差最后一个元素相交

解法 2：双指针，走完 A+B 最优解

思路

1. 双指针 p1 和 p2，分别指向 headA 和 headB
2. 如果用两个指针 p1 和 p2 分别在两条链表上前进，并不能同时走到公共节点，也就无法得到相交节点 c1
3. 我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1

疑问
如果两条链表不相交，会死循环吗？看上图，相当于 p1 走到 b3，p2 走到 a2，如果两条链不相交的话，p1.next=null 且 p2.next=null，while 循环就退出了

a1→a2→c1→c2→c3→b1→b2→b3→c1 b1→b2→b3→c1→c2→c3→a1→a2→c1

如果 A 和 B 不想交，那么会是怎样？ A：a1→a2→a3→null B：b1→b2→b3→b4→null a1→a2→a3→b1→b2→b3→b4→null b1→b2→b3→b4→a1→a2→a3→null

代码

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode p1 = headA;
    ListNode p2 = headB;
    while (p1 != p2) {
        if (p1 == null) { // p1走完，指向headB继续走
            p1 = headB; 
        } else {
            p1 = p1.next;
        }
        if (p2 == null) { // p2走完，指向headA继续走
            p2 = headA;
        } else {
            p2 = p2.next;
        }
    }
    return p1;
}

复杂度
空间复杂度为 O(1)，时间复杂度为 O(N)

解法 3：先计算长度，然后计算差值，遍历

1. 先计算 2 条链表的长度，lenA 和 lenB
2. 再从长的那条链表开始遍历，让其走 lenA-lenB（假如 lenA 比 lenB 长），目的是让他们跑到一起；如果两条链表相交，不相交的部分其实多出来了 lenA-lenB，让 A 先跑追上 A 就是让两条链表在同一起跑线上
3. 然后再让两条链表一起跑，如果出现节点相同，就出现相交；如果循环结束那就不相交

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    // 先计算长度
    int l1 = 0;
    ListNode temp1 = headA;
    while (temp1 != null) {
        l1++;
        temp1 = temp1.next;
    }
    int l2 = 0;
    ListNode temp2 = headB;
    while (temp2 != null) {
        l2++;
        temp2 = temp2.next;
    }


    temp1 = headA;
    temp2 = headB;
    if (l2 > l1) {
        // 先跑B
        for (int i = 0; i < l2 - l1; i++) {
            temp2 = temp2.next;
        }
    } else if (l1 > l2) {
        // 先跑A
        for (int i = 0; i < l1 - l2; i++) {
            temp1 = temp1.next;
        }
    }
    // 再一起跑
    while (temp1 != temp2) {
        temp1 = temp1.next;
        temp2 = temp2.next;
    }
    return temp2;
}

解法 4：将链表转换为环

如果把两条链表首尾相连，那么「寻找两条链表的交点」的问题转换成了前面讲的「寻找环起点」的问题：不过需要注意的是，这道题说不让你改变原始链表的结构，所以你把题目输入的链表转化成环形链表求解之后记得还要改回来，否则无法通过。

链表相加

反转链表解法

public ListNode addInList(ListNode head1, ListNode head2) {
    // 判空
    if (head1 == null) return head2;
    if (head2 == null) return head1;

    // 反转链表
    ListNode head1Reverse = reverse(head1);
    System.out.println("反转head1后=" + head1Reverse);
    ListNode head2Reverse = reverse(head2);
    System.out.println("反转head2后=" + head2Reverse);

    // 创建新的链表头节点
    ListNode newHeadNode = new ListNode(-1);
    ListNode newNode = newHeadNode;

    // 记录进位的数值: 各取链表的一位相加，超过10就进位
    int tmp = 0;
    while (head1Reverse != null || head2Reverse != null) {
        int count = tmp; // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值） : 首先加上上一次的进位值
        // 当节点1不为空的时候，则需要加上当前节点的值
        if (head1Reverse != null) {
            count += head1Reverse.val;
            head1Reverse = head1Reverse.next;
        }
        // 当节点2不为空的时候，则需要加上当前节点的值
        if (head2Reverse != null) {
            count += head2Reverse.val;
            head2Reverse = head2Reverse.next;
        }
        tmp = count / 10; // 求出进位：作为下一次进位用
        int value = count % 10; // 取余，进位后剩下的数值即为当前节点的数值
        System.out.println("count=" + count + "，tmp(进位值)=" + tmp + "，当前节点val=" + value);
        newNode.next = new ListNode(value);
        newNode = newNode.next;
    }
    // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
    if (tmp != 0) {
        newNode.next = new ListNode(tmp);
    }
    System.out.println("最后的结果=" + newHeadNode.next);
    // 重新反转回来返回
    return reverse(newHeadNode.next);
}

// 反转链表
private ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;

        // 每遍历一个节点，将当前节点指向前一个节点
        cur.next = pre;

        pre = cur;
        cur = next;
    }
    return pre;
}

单链表的排序

解法 1：借助数组

值排序，不是真正做到链表排序，直接遍历整个链表，用一个数组存储所有的 val，然后进行排序，最后将排序完的值赋值给链表

public ListNode sortInList2(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ArrayList<Integer> list = new ArrayList<>();
    ListNode tmp = head;
    while (tmp != null) {
        list.add(tmp.val);
        tmp = tmp.next;
    }
    list.sort(Comparator.comparingInt(a -> a));
    ListNode temp = head;
    int i = 0;
    while (temp != null) {
        temp.val = list.get(i++);
        temp = temp.next;
    }
    return head;
}

解法 2：归并排序思想

先利用快慢指针找出链表的中点，然后分为两个链表，一直分，知道无法分为止，然后自底而上排序归并

public ListNode sortInList(ListNode head) {
    if (head == null || head.next == null) return head;
    // 找到链表中间节点
    ListNode centerListNode = getCenterListNode(head);
    // 拆分开
    ListNode head1 = head;
    ListNode head2 = centerListNode.next;
    centerListNode.next = null;
    // 归并排序

    // 先拆成左右2个链表
    ListNode left = sortInList(head1);
    ListNode right = sortInList(head2);

    // 再把拆分的两个有序链表合并
    return mergeList(left, right);
}

/**
 * 合并两个有序链表：这里比较巧妙，这是一个针对有序链表的写法，但是我们的拆分明明是不能保证有序的，哈哈，巧在当我们在不停的分治的过程中，最后一定是有单节点的合并的，两个单节点可以认为就是两个有序的链表，两个单节点的合并就是两个有序链表的合并，也就是说两个单节点链表合并成了一个拥有两个节点的有序链表，再继续向上回溯，从下网上就形成了两个有序链表的合并了。
 */
private ListNode mergeList(ListNode list1, ListNode list2) {
    // 新的存储节点
    ListNode newDummyNode = new ListNode(-1);
    ListNode cur = newDummyNode;

    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
    }
    if (list1 != null) {
        cur.next = list1;
    }
    if (list2 != null) {
        cur.next = list2;
    }
    return newDummyNode.next;
}

234. 回文链表 easy

题目

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。 输入：head = [1,2,2,1] 输出：true

解法 1：借助 List

思路

1. 先将链表全部添加到 List 中去
2. 首尾双指针遍历判断是否回文结构

public boolean isPalindrome(ListNode head) {
    // write code here
    // n==1，返回true
    if (head.next == null) {
        return true;
    }
    List<Integer> nums = new ArrayList<Integer>();
    // 将链表转换成list
    while (head != null) {
        nums.add(head.val);
        head = head.next;
    }
    int i = 0;
    int j = nums.size() - 1;
    while (i < j) {
        // 不等则返回false
        // 这边有一个坑，如果不适用equals而使用!=的话，在牛客上对于有负数的测试用例可能会无法通过。
        if (!nums.get(i).equals(nums.get(j))) {
            return false;
        }
        ++i;
        --j;
    }
    return true;
}

解法 2：递归，后序位置

思路

1. 单链表是无法倒序遍历的，我们可以利用链表递归的后序遍历，由于后序位置的输出是倒序，那么我们就可以在链表后序的位置进行回文结构的判断；
2. 用一个临时节点 left 记录当前比较的节点
3. 比较 left 和每次入栈的节点

题解
如何判断回文链表 :: labuladong的算法小抄

代码

public static boolean isPalindrome(ListNode head) {
    left = head;
    return traverse(head);
}
private static ListNode left;
private static boolean traverse(ListNode head) {
    if (head==null) return true;
    // 前序位置
    boolean res = traverse(head.next);
    // 后序位置：倒序的
    // head.next是否是回文链表和当前节点是否回文结构计算
    res = res && (head.val == left.val);
    left = left.next;
    return res;
}

解法 3：快慢指针 + 反转链表 最优解

思路

1. 快慢指针 fast/slow 找到中间节点，中间节点就是 slow（如果链表偶数个数，中间节点为靠后的那个）
2. 判断链表奇数偶数，根据 fast 来判断，最后 fast=null 是奇数个数，最后 fast!=null 是偶数个数
3. 反转后半部分链表（可以将链表断开）
4. 逐个比较前后两段链表元素是否相同

public boolean isPalindrome(ListNode head) {
    if(head==null) return false;
    if(head.next==null) return true;
    // 先找到中点
    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
	// 中点就是slow

    // 判断链表奇数偶数，看fast
    ListNode l1 = null;
    ListNode l2 = null;
    if(fast == null) { // 偶数
        l1 = head;
        l2 = slow;
    } else { // 奇数
        l1 = head;
        l2 = slow.next;
    }

    // 反转中点后的链表（迭代法）
    ListNode cur = l2;
    ListNode pre = null;
    while(cur != null) {
        ListNode next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

    // 比较前后链表, l1是前半部分链表，pre是后半部分链表
    while(l1!=null && pre!=null) {
        if(pre.val != l1.val) {
            return false;
        }
        l1 = l1.next;
        pre = pre.next;
    }
    return true;
}

链表实现栈和队列？

1、链表实现队列

两个单链表，一个 head 指向头节点，一个 tail 指向尾节点

2、链表实现栈

一个单链表即可，head 指向头节点
链表的奇偶重排
拆分成 2 个链表，奇链表和偶链表，最后将偶链表添加到奇链表后面

86. 分隔链表（单链表的分解） medium

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你应当 保留 两个分区中每个节点的初始相对位置。

解法 1：两个个临时链表 + 合并

思路

1. 两个临时链表，dummy1 存放比 x 小的节点，dummy2 存储不比 x 小的节点
2. 遍历链表，将链表分割到 dummy1 和 dummy2l 链表中去
3. 将两个链表重新连接起来
4. 最后返回 dummy1.next

代码

public static ListNode partition(ListNode head, int x) {
    // 存放比x小的节点
    ListNode dummy1 = new ListNode(0);
    ListNode node1 = dummy1;
    // 存放不比x小的节点
    ListNode dummy2 = new ListNode(0);
    ListNode node2 = dummy2;
    while (head != null) {
        if (head.val < x) {
            node1.next = head;
            node1 = node1.next;
        } else {
            node2.next = head;
            node2 = node2.next;
        }
        ListNode next = head.next;
        // 断开原链表中的每个节点的 next 指针
        head.next = null;
        head = next;
    }
    // 连接dummy1和dummy2
    node1.next = dummy2.next;
    return dummy1.next;
}