力扣刷题：链表篇

￡神魔★判官ぃ 2022-10-16 09:40 268阅读 0赞

### 目录 ###

*  1290. 二进制链表转整数
 *   *  题目介绍
     *  题目实现
 *  138. 复制带随机指针的链表
 *   *  题目介绍
     *   *   *  \[剑指 Offer 35. 复杂链表的复制\](https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/)
     *  题目实现
 *  141. 环形链表
 *   *  题目介绍
     *  题目实现
 *  160. 相交链表
 *   *  题目介绍
     *   *   *  \[面试题 02.07. 链表相交\](https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/)
             *  \[剑指 Offer 52. 两个链表的第一个公共节点\](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
     *  题目实现
 *  2. 两数相加
 *   *  题目介绍
     *   *   *  \[面试题 02.05. 链表求和\](https://leetcode-cn.com/problems/sum-lists-lcci/)
     *  题目实现
 *  203. 移除链表元素
 *   *  题目介绍
     *   *   *  \[剑指 Offer 18. 删除链表的节点\](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/)
     *  题目实现
 *  206. 反转链表
 *   *  题目介绍
     *   *   *  \[剑指 Offer 24. 反转链表\](https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/)
             *  \[剑指 Offer II 024. 反转链表\](https://leetcode-cn.com/problems/UHnkqh/)
     *  题目实现
 *  21. 合并两个有序链表
 *   *  题目介绍
     *   *   *  \[剑指 Offer 25. 合并两个排序的链表\](https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)
     *  题目实现
 *  23. 合并K个升序链表
 *   *  题目介绍
     *   *   *  \[21. 合并两个有序链表\](https://leetcode-cn.com/problems/merge-two-sorted-lists/)
     *  题目实现
 *  234. 回文链表
 *   *  题目介绍
     *   *   *  \[面试题 02.06. 回文链表\](https://leetcode-cn.com/problems/palindrome-linked-list-lcci/)
             *  \[206. 反转链表\](https://leetcode-cn.com/problems/reverse-linked-list/)
             *  \[876. 链表的中间节点\](https://leetcode-cn.com/problems/middle-of-the-linked-list/)
     *  题目实现
 *  86. 分隔链表
 *   *  题目介绍
     *   *   *  \[面试题 02.04. 分割链表\](https://leetcode-cn.com/problems/partition-list-lcci/)
     *  题目实现
 *  876. 链表的中间结点
 *   *  题目介绍
     *  题目实现
 *  92. 反转链表 II
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 06. 从尾到头打印链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 18. 删除链表的节点
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 22. 链表中倒数第k个节点
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 24. 反转链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 25. 合并两个排序的链表
 *   *  题目介绍
     *  题目实现
 *  剑指 Offer 35. 复杂链表的复制
 *   *  题目介绍
     *   *   *  \[138. 复制带随机指针的链表\](https://leetcode-cn.com/problems/copy-list-with-random-pointer/)
     *  题目实现
 *  面试题 02.08. 环路检测
 *   *  题目介绍
     *   *   *  \[141. 环形链表\](https://leetcode-cn.com/problems/linked-list-cycle/)
     *  题目实现

--------------------

# 1290. 二进制链表转整数 #

## 题目介绍 ##

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

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

**示例 1：**

![d0dff411f5aa117923e76cd52df9c221.png][]

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

**示例 2：**

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

**示例 3：**

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

**示例 4：**

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

**示例 5：**

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

**提示：**

*  链表不为空。
 *  链表的结点总数不超过 30。
 *  每个结点的值不是 0 就是 1。

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

## 题目实现 ##

由于链表中从高位到低位存放了数字的二进制表示，因此我们可以使用二进制转十进制的方法，在遍历一遍链表的同时得到数字的十进制值。以示例 1 中给出的二进制链表为例：

![dccf83198c361ca1b10f6d9f705a6e6d.png][]

以下用 `(n)2` 表示 n 是二进制整数。

![4af3ffd1b08e70ce688a0987bc370e8b.png][]

链表的第 1 个节点的值是 1，这个 1 是二进制的最高位，在十进制分解中，1 作为系数对应的 22 的指数是 2，这是因为链表的长度为 3。我们是不是有必要一定要先知道链表的长度，才可以确定指数 2 呢？答案是不必要的。

正常计算：数 ÷ 2 = 商 …… 余数
    5 ÷ 2 = 2 余 1
    2 ÷ 2 = 1 余 0
    1 ÷ 2 = 0 余 1
    ===> 得出二进制 101
    
    反推回去：商 x 2 + 余数 = 数
    -> 0 x 2 + 1 = 1
    -> 1 x 2 + 0 = 2
    -> 2 x 2 + 1 = 5
    ===> 得出十进制 5

class Solution { 
        public int getDecimalValue(ListNode head) { 
            int ans = 0;
            while (head != null) { 
                ans = ans * 2 + head.val;
                head = head.next;
            }
            return ans;
        }
    }

# 138. 复制带随机指针的链表 #

## 题目介绍 ##

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

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

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

返回复制链表的头节点。

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

*  `val`：一个表示 `Node.val` 的整数。
 *  `random_index`：随机指针指向的节点索引（范围从 `0` 到 `n-1`）；如果不指向任何节点，则为 `null` 。

你的代码 **只** 接受原链表的头节点 `head` 作为传入参数。

**示例 1：**

![3a67d02d04b53c0132cbc6dd04cf2066.png][]

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

**示例 2：**

![3a67d02d04b53c0132cbc6dd04cf2066.png][]

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

**示例 3：**

![e294e891355d101c2ec7457654c26cdd.png][]

输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

**示例 4：**

输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

**提示：**

*  0 <= n <= 1000
 *  \-10000 <= Node.val <= 10000
 *  Node.random 为空（null）或指向链表中的节点。

**相同题目：**

*  #### [剑指 Offer 35. 复杂链表的复制][Offer 35.] ####

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

## 题目实现 ##

我们遍历整个链表，在遍历的过程中，以 **旧节点** 为 **键** ，**新节点** 为 **值** 储存在哈希表中。

然后再次遍历整个链表，通过 **旧节点** 拿到 **新节点** ，然后为 **新节点** 进行 `next` 和 `random` 赋值即可。

# 141. 环形链表 #

## 题目介绍 ##

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 `pos` 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 `pos` 是 -1，则在该链表中没有环。

注意：`pos` 不作为参数进行传递，仅仅是为了标识链表的实际情况。

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

**示例 1：**

![2c693f31894ccbcbb3cf116203bd2e76.png][]

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

**示例 2：**

![000233190926e2bc48c72b33dc5d7950.png][]

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

**示例 3：**

![39e0fc435ad7fdd1897b541828b5da7d.png][]

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

**提示：**

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

**进阶：**

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

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

## 题目实现 ##

解决环形链表我们需要使用到快慢指针，快指针每次移动两个节点，慢指针每次移动一个节点，举个生动形象的例子：

运动会跑步5000米，跑的快的人肯定有机会能够追得上跑得慢的人，同理这就是快慢指针的原理。

在判断一个链表是否有环，我们不妨先来看看，链表无环的情况，链表的节点的个数可能为奇数也可能为偶数，下面给出两种情况图示：

当链表个数为奇数的时候，快指针每次走两个节点，慢指针每次走一个节点，过程如下：

![b878e97bd5d1a3b284fc451a9fdcbcfb.png][]

![522917e96b6788cd2b02e0abe15c711a.png][]

![c33319c83099c5212085641817077a71.png][]

此时，我们发现 fast 指针已经指到了最后一个元素的位置，此时，slow 指针正好指向最中间的元素，结束条件则为：`fast.next = null` 。

当链表个数为偶数的时候，快指针每次走两个节点，慢指针每次走一个节点，过程如下：

![68cf2cc81187b5762bc819648be3f803.png][]

![58e61fdfa2a842d17d9a7895d32624d0.png][]

![6d84a7a4cd71785c24280c9be0248ce5.png][]

![a2ebae794253c71cedf163d10f5ff19f.png][]

此时，我们发现 fast 指针已经指到了 `null` 位置，此时，结束条件则为：`fast = null` 。

通过上面两种图示的情况分析，只要链表不存在环，那就说明到最后快指针一定满足：`fast == null || fast.next == null` 。

如果链表存在环，那么 **快指针** 和 **慢指针** 总会在某一时刻相交，相交则证明有环，就好比操场的圆形跑道一样。

public class Solution { 
        public boolean hasCycle(ListNode head) { 
            if (head == null) return false;
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) { 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) return true;
            }
            return false;
        }
    }

# 160. 相交链表 #

## 题目介绍 ##

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

如下面的两个链表：

![7e2337a97e87e0872b189dd6f8c6f48c.png][]

在节点 c1 开始相交。

**示例 1：**

![42fab0317e87fd4e667d349639bbb1a0.png][]

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

**示例 2：**

![337df24355af0f2c8f4f8e9f2e94b556.png][]

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

**示例 3：**

![f97e63af7cae4054c69a612dcce6c7ff.png][]

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

**注意：**

*  如果两个链表没有交点，返回 null。
 *  在返回结果后，两个链表仍须保持原有的结构。
 *  可假定整个链表结构中没有循环。
 *  程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

**相同题目：**

*  #### [面试题 02.07. 链表相交][02.07.] ####
 *  #### [剑指 Offer 52. 两个链表的第一个公共节点][Offer 52.] ####

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

## 题目实现 ##

![42fab0317e87fd4e667d349639bbb1a0.png][]

我们拿到这道题，会感觉有点困难，有点无从下手，其实我们不妨换个角度来看，如下图：

![b7b50c17bcaab25584099091144b6813.png][]

我们只需要把A链表的长度和B链表的长度补齐，然后从左向右依次判断下图第一行中的节点和下图第二行中的节点地址是否相等即可。

![25e7341bd60f5204859959138df5e8d6.png][]

就拿上图补全后的第一行来说，一旦扫描完毕A链表发现没有相交的节点，当扫描到链表尾部，发现 `curA == null` ，他会立刻开始从B链表开始向后搜索，直到找到一个 **地址值** 相等的节点，那就意味着找到了一个相交的节点，即使B链表搜索了一遍也没找到，那也没关系，由于补全后上图上下两行链表的长度是一样的，到最后都会扫描到 null，由于 `null == null` 是相等的，循环自然会退出，并且此时返回 curA 也就是 null，也是正确的。

public class Solution { 
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) { 
            if (headA == null || headB == null) return null;
            ListNode curA = headA;
            ListNode curB = headB;
            while (curA != curB) { // 注意：这里判断的是地址值
                curA = (curA == null) ? headB : curA.next;
                curB = (curB == null) ? headA : curB.next;
            }
            return curA;
        }
    }

# 2. 两数相加 #

## 题目介绍 ##

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

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

**示例 1：**

![c243036a8ff06695054a0bea2ba22996.png][]

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

**示例 2：**

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

**示例 3：**

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

**提示：**

*  每个链表中的节点数在范围 \[1, 100\] 内
 *  0 <= Node.val <= 9
 *  题目数据保证列表表示的数字不含前导零

**相同题目：**

*  #### [面试题 02.05. 链表求和][02.05.] ####

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

## 题目实现 ##

将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如 `987 + 23 = 987 + 023 = 1010`。

每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值。

class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            ListNode newHead = new ListNode(0);
            ListNode newLast = newHead;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0) { 
                // 为空默认零
                int l1Val = l1 != null ? l1.val : 0;
                int l2Val = l2 != null ? l2.val : 0;
                // 两数来相加
                int sumVal = l1Val + l2Val + carry;
                // 更新进位值
                carry = sumVal / 10;
                // 保存个位数
                ListNode sumNode = new ListNode(sumVal % 10);
                newLast.next = sumNode;
                newLast = sumNode;
                // 分别向后移
                if (l1 != null) l1 = l1.next;
                if (l2 != null) l2 = l2.next;
            }
            return newHead.next;
        }
    }

# 203. 移除链表元素 #

## 题目介绍 ##

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

**示例 1：**

![2893cc7780a00288e0e7bed67c87d6a5.png][]

输入：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 <= k <= 50

**相同题目：**

*  #### [剑指 Offer 18. 删除链表的节点][Offer 18.] ####

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

## 题目实现 ##

我们可以创建一个新的链表，遍历原链表中的节点，如果该节点的值和 val 的值不相等，就追加到新链表中。为了方便追加，我们还需要设置一个 newlast 指针，指向最后一个节点，初始化的时候：newHead、newLast应该指向同一个节点。已知给定 val = 6。

![45556eed0262caf9c2c61c3ac75a2f8b.png][]

当 head 指针指向原链表的 **1节点** ，与给定的 val 不相符，追加到新链表。此时应该让 newLast 的下个节点指向 head，然后让 newLast 指向 head 节点，以上操作完成，head 指针需要向后移动一位，也就是 `head = head.next;` 。

![dea5be6f67abed0bb28f0d63d9c323d6.png][]

当 head 指针指向原链表的 **2节点** ，与给定的 val 不相符，追加到新链表。此时应该让 newLast 的下个节点指向 head，然后让 newLast 指向 head 节点，以上操作完成，head 指针需要向后移动一位，也就是 `head = head.next;` 。

![f4322e72ad8b47ab110d50a2e8d46a1b.png][]

当 head 指针指向原链表的 **6节点** ，与给定的 val 相等，说明此次不需要进行追加操作，但是head 指针需要向后移动一位，也就是 `head = head.next;` 。

![ba58970738a37bb863bc7609d68d8982.png][]

按照上述的操作，一直向后扫描进行，直到 head 为 null 的时候退出，此时，我们的任务已经完成了一大半，还有一个小问题，那就是 newLast 所指向的节点的下一个节点并不为 null，我们需要手动设置为 null，这一步很重要，否则，答题不能通过。

![d9ca4aa38feb2eb2d30a5deecd796793.png][]

class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            ListNode newHead = new ListNode(0);
            ListNode newLast = newHead;
            while (head != null) { 
                if (head.val != val) { 
                    newLast.next = head;
                    newLast = head;
                }
                head = head.next;
            }
            newLast.next = null;
            return newHead.next;
        }
    }

# 206. 反转链表 #

## 题目介绍 ##

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

**示例 1：**

![f2df6442a49e780cfa2859ee67cb6d38.png][]

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

**示例 2：**

![039b5bf72410768a2d16c54a0f4b0adb.png][]

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

**示例 3：**

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

**提示：**

*  链表中节点的数目范围是 \[0, 5000\]
 *  \-5000 <= Node.val <= 5000

**相同题目：**

*  #### [剑指 Offer 24. 反转链表][Offer 24.] ####
 *  #### [剑指 Offer II 024. 反转链表][Offer II 024.] ####

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

## 题目实现 ##

![c7b0c6667d82b95e7e6f6dbb326bc06c.png][]

对于链表的反转，我们首先需要定义一个新的链表头，从左到右扫描原链表所有节点，然后依次追加到新表头的左边即可。

首先先缓存住当前 head 节点的下一个节点，也就是 **2节点** ，因为我们要对 head 节点进行操作，让 head 节点的 next 指向 newHead，然后让 newHead 指向 head，然后让 head 重新指向缓存住的 **2节点**，完成上述操作后，如下图：

![c5fbfb28c081d307a6b924fb7485c627.png][]

然后再缓存住当前 head 节点的下一个节点，也就是 **3节点** ，因为我们要对 head 节点进行操作，让 head 节点的 next 指向 newHead，然后让 newHead 指向 head，然后让 head 重新指向缓存住的 **3节点**，完成上述操作后，如下图：

![a03bac3016163e9b0bff2542107fbc33.png][]

然后再缓存住当前 head 节点的下一个节点，也就是 **null节点** ，因为我们要对 head 节点进行操作，让 head 节点的 next 指向 newHead，然后让 newHead 指向 head，然后让 head 重新指向缓存住的 **null节点**，完成上述操作后，如下图：

![342659eed7ff98d8bf7beca0a26ae577.png][]

经过上述操作后，此时 head 节点为 null ，结束循环，然后返回 newHead 即可。

class Solution { 
        public ListNode reverseList(ListNode head) { 
            ListNode newHead = null;
            ListNode tmpNode = null;
            while (head != null) { 
                tmpNode = head.next;
                head.next = newHead;
                newHead = head;
                head = tmpNode;
            }
            return newHead;
        }
    }

# 21. 合并两个有序链表 #

## 题目介绍 ##

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

**示例 1：**

![1fafb784c2e5351c232f322e6f98e08e.png][]

输入：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 均按 非递减顺序 排列

**相同题目：**

*  #### [剑指 Offer 25. 合并两个排序的链表][Offer 25.] ####

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

## 题目实现 ##

![286420205408102de04838ec912bae23.png][]

我们需要创建一个虚拟头部，然后循环同时遍历 l1 和 l2 所指向的节点，如果 l1.val <= l2.val ，我们就追加到虚拟头部节点之上。

![22eba2fe4cec6fbdd89ec7530db6cac9.png][]

![5fec0cde3f996ca5e872e40e9e171f66.png][]

![0af2781e2457faf807a5759d7ad957e4.png][]

![796382fc0032e19e3a0f9cfff9bf8147.png][]

![960d451ba8482e236ec6ee90497bccbb.png][]

![64dc70cd46871063afd5411684949002.png][]

![7715ab287ccad4885b52a2d58f9d26fa.png][]

![895db150f648fb3be8a8278b17ba568d.png][]

此时，我们发现 l1 指向为 null，那我们就退出循环，然后把 l2 直接追加到 newLast 上就好了。

![902af78a571c1ff049250252755b4a22.png][]

经过上述的操作，我们只需要返回 newHead.next 即可。

class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            ListNode newHead = new ListNode(0);
            ListNode newLast = newHead;
            while (l1 != null && l2 != null) { 
                if (l1.val <= l2.val) { 
                    newLast.next = l1;
                    newLast = l1;
                    l1 = l1.next;
                } else { 
                    newLast.next = l2;
                    newLast = l2;
                    l2 = l2.next;
                }
            }
    
            if (l1 != null) newLast.next = l1;
            if (l2 != null) newLast.next = l2;
    
            return newHead.next;
        }
    }

# 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 <= 104
 *  0 <= lists\[i\].length <= 500
 *  \-104 <= `lists[i][j]` <= 104
 *  lists\[i\] 按 升序 排列
 *  lists\[i\].length 的总和不超过 104

**用到题目：**

*  #### [21. 合并两个有序链表][21.] ####

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

## 题目实现 ##

实现思路其实很简单，我们只需要把给定的数组中的链表，两两合并，直到剩下一条链表为止，就完成了所有链表的合并，图解如下：

![2b20937a09c2e8ac4db9120729e31f8b.png][]

class Solution { 
        // https://leetcode-cn.com/problems/merge-k-sorted-lists/
        public ListNode mergeKLists(ListNode[] lists) { 
            if (lists == null || lists.length == 0) return null;
    
            int step = 1;
            while (step < lists.length) { 
                int nextStep = step * 2;
                for (int i = 0; i + step < lists.length; i += nextStep) { 
                    lists[i] = mergeTwoLists(lists[i], lists[i + step]);
                }
                step = nextStep;
            }
    
            return lists[0];
        }
    
        // https://leetcode-cn.com/problems/merge-two-sorted-lists/
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            if (l1 == null) return l2;
            if (l2 == null) return l1;
    
            ListNode newHead = new ListNode(0);
            ListNode newLast = newHead;
            while (l1 != null && l2 != null) { 
                if (l1.val <= l2.val) { 
                    newLast.next = l1;
                    newLast = l1;
                    l1 = l1.next;
                } else { 
                    newLast.next = l2;
                    newLast = l2;
                    l2 = l2.next;
                }
            }
    
            if (l1 != null) newLast.next = l1;
            if (l2 != null) newLast.next = l2;
    
            return newHead.next;
        }
    }

# 234. 回文链表 #

## 题目介绍 ##

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

**示例 1：**

输入: 1->2
    输出: false

**示例 2：**

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

**进阶：**

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

**相同题目：**

*  #### [面试题 02.06. 回文链表][02.06.] ####

**用到题目：**

*  #### [206. 反转链表][206.] ####
 *  #### [876. 链表的中间节点][876.] ####

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

## 题目实现 ##

我们想要判断链表是不是回文链表，需要首先找到这条链表的中间节点，对于链表的个数为偶数时，有两个中间节点，则使用第二个中间节点为中间节点。然后对以中间节点开始的右半部分链表进行反转操作，反转完成以后，只需要通过逐个对比 lHead 和 rHead 所对应的元素是不是一样的就行，可以参照下图的第二张图，比较明显，判断完成以后，我们需要恢复对右半部分链表的反转。

![38ff2cb704fb5f302657a70c4d068b2f.png][]

class Solution { 
        // https://leetcode-cn.com/problems/palindrome-linked-list/
        public boolean isPalindrome(ListNode head) { 
            // 临界条件检查
            if (head == null || head.next == null) return true;
            // 找到中间节点
            ListNode midNode = middleNode(head);
            // 反转右半部分
            ListNode newHead = reverseList(midNode);
            // 重新定义变量
            ListNode lHead = head;
            ListNode rHead = newHead;
            // 开始进行判断
            boolean isPalindrome = true;
            while (lHead != null && rHead != null) { 
                if (lHead.val != rHead.val) { 
                    isPalindrome = false;
                    break;
                }
                lHead = lHead.next;
                rHead = rHead.next;
            }
            // 恢复右半部分
            reverseList(newHead);
            // 返回判定结果
            return isPalindrome;
        }
    
        // https://leetcode-cn.com/problems/middle-of-the-linked-list/
        public ListNode middleNode(ListNode head) { 
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) { 
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    
        // https://leetcode-cn.com/problems/reverse-linked-list/
        public ListNode reverseList(ListNode head) { 
            ListNode newHead = null;
            ListNode tmpNode = null;
            while (head != null) { 
                tmpNode = head.next;
                head.next = newHead;
                newHead = head;
                head = tmpNode;
            }
            return newHead;
        }
    }

# 86. 分隔链表 #

## 题目介绍 ##

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

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

![327258c0edc0fc5daf5c7fae8e651115.png][]

**示例 1：**

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

**示例 2：**

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

**提示：**

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

**相同题目：**

*  #### [面试题 02.04. 分割链表][02.04.] ####

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

## 题目实现 ##

![327258c0edc0fc5daf5c7fae8e651115.png][]

我们现在需要对链表进行分隔，使得所有 **小于** `x` 的节点都出现在 **大于或等于** `x` 的节点之前。

因此，我们就创建两个新的头节点，一个为左头节点，一个为右头节点，左头节点存储**小于** `x` 的节点，而右头节点存储**大于或等于** `x` 的节点，为了方便进行添加新节点，我们再分别对应创建两个指向尾节点的指针，如下图：

![bad38b3e0b1e3ba7be457143ff225cf8.png][]

循环遍历原链表中的所有节点，遇到 **小于** `x` 的节点放到左链表上，遇到 **大于或等于** `x` 的节点放到右链表上。

目前 head 指向为 **1节点** ，小于x，因此直接连到左链表上，然后 head 向后移动一个节点。

![22dee0aa354d948138e0a1deeb7da32d.png][]

然后 head 指向为 **4节点** ，大于x，因此直接连到右链表上，然后 head 向后移动一个节点。

![205d671709db39281e6c6d89224d1b17.png][]

按照上边的规则，从左向右依次扫描原链表的所有节点，直到遇见 `null` 节点停止，然后把左链表和右链表拼接到一块基本就行了。

但是要注意，右链表的最后一个元素，也就是 `rLast` 所指向的节点的 `next` 引用并不一定是为 `null` 的，因此，我们需要手动设置。

class Solution { 
        public ListNode partition(ListNode head, int x) { 
            if (head == null) return null;          // 传入链表为空判断
            ListNode lHead = new ListNode(0);   // 创建虚拟左头节点
            ListNode rHead = new ListNode(0);   // 创建虚拟右头节点
            ListNode lLast = lHead;     // 默认左边的last指向左边的head
            ListNode rLast = rHead;     // 默认右边的last指向右边的head
            while (head != null) { 
                if (head.val < x) { 
                    lLast.next = head;
                    lLast = head;
                } else { 
                    rLast.next = head;
                    rLast = head;
                }
                head = head.next;
            }
            lLast.next = rHead.next;    // 两个链表进行拼接
            rLast.next = null;          // 去除最后节点指向
            return lHead.next;          // 返回链表首个元素
        }
    }

# 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 之间。

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

## 题目实现 ##

我们采用快慢指针来实现链表中间结点的查找，一般来说，一个链表的个数只可能有两种情况，奇数或者偶数，我们分别探讨一下。

当链表个数为奇数的时候，快指针每次走两个结点，慢指针每次走一个结点，过程如下：

![a43d7e4b764609cd1b3136a8410acc3d.png][]

![3a0ae5d87b5fe2f09e68c23a67ff68ba.png][]

![e855078e933bfae3b3521e1312bde05a.png][]

此时，我们发现 fast 指针已经指到了最后一个元素的位置，此时，slow 指针正好指向最中间的元素，结束条件则为：`fast.next = null` 。

当链表个数为偶数的时候，快指针每次走两个结点，慢指针每次走一个结点，过程如下：

![b5539b6bc4c173da2bf0625b0fa71ec2.png][]

![7ec2af5b7667a59297dd0db7328aa68d.png][]

![34da4f56034ef42c99994addf90f6987.png][]

![a2ebae794253c71cedf163d10f5ff19f.png][]

此时，我们发现 fast 指针已经指到了 `null` 位置，此时，由于该链表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

slow 指针正好指向最中间的第二个结点4，结束条件则为：`fast = null` 。

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

![75fe740429424f9ee47646c5e77327ec.png][]

试想一下，如果我们拓展一下这道题目，首先奇数的情况都一样，这里就不考虑了。当链表的个数为偶数的时候，以上图为例，由于该链表有两个中间结点，值分别为 3 和 4，我们返回第一个结点。又该如何实现呢？

![5fee9e29bdc0b73a5d6152d4f6e0e5b2.png][]

![2da642f8a2ba5ec9e765b966e8589d63.png][]

![5137e59c16a142a0f9c14424ed0db6b0.png][]

我们发现当快指针 fast 走到倒数第二个元素位置的时候，慢指针 slow 正好处于两个中间结点的第一个位置处，结束条件则为：`fast.next.next = null`。

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

# 92. 反转链表 II #

## 题目介绍 ##

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

**示例 1：**

![74350afa7274adc1592ae077fc9592b6.png][]

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

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

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

## 题目实现 ##

1、我们定义两个指针，分别称之为 g(guard 守卫) 和 p(point 指针)。  
我们首先根据方法的参数 m 确定 g 和 p 的位置。将 g 移动到第一个要反转的节点的前面，将 p 移动到第一个要反转的节点的位置上。我们以 m=2，n=4为例。  
2、将 p 后面的元素删除，然后添加到 g 的后面。也即头插法。  
3、根据 m 和 n 重复步骤（2）  
4、返回 dummyHead.next

![136e7ff929037fc035b8f8ee132500f6.png][]

![b0527504fb6f01a42c4c7147e8400e71.png][]

class Solution { 
        public ListNode reverseBetween(ListNode head, int left, int right) { 
            //创建虚拟头部
            ListNode dummyHead = new ListNode();
            dummyHead.next = head;
            //创建两个指针
            ListNode g = dummyHead;
            ListNode p = dummyHead.next;
            //移动到起始处
            for (int i = 0; i < left - 1; i++) { 
                g = g.next;
                p = p.next;
            }
            //反转到结束处
            for (int i = 0; i < right - left; i++) { 
                ListNode removed = p.next;
                p.next = p.next.next;
                removed.next = g.next;
                g.next = removed;
            }
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

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

**示例 1：**

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

**限制：**

*  0 <= 链表长度 <= 10000

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

## 题目实现 ##

栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。

class Solution { 
        public int[] reversePrint(ListNode head) { 
            Stack<ListNode> stack = new Stack<>();
            while (head != null) { 
                stack.push(head);
                head = head.next;
            }
            int size = stack.size();
            int[] arr = new int[size];
            for (int i = 0; i < size; i++) { 
                arr[i] = stack.pop().val;
            }
            return arr;
        }
    }

# 剑指 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 被删除的节点

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

## 题目实现 ##

class Solution { 
        public ListNode deleteNode(ListNode head, int val) { 
            ListNode dummyHead = new ListNode();
            dummyHead.next = head;
            ListNode q = dummyHead;
            ListNode p = dummyHead.next;
            while (p != null) { 
                if (p.val == val) { 
                    q.next = q.next.next;
                    break;
                }
                q = q.next;
                p = p.next;
            }
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

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

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

**示例：**

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

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public ListNode getKthFromEnd(ListNode head, int k) { 
            ListNode q = head;
            ListNode p = head;
            for (int i = 0; i < k; i++) { 
                p = p.next;
            }
            while (p != null) { 
                q = q.next;
                p = p.next;
            }
            return q;
        }
    }

# 剑指 Offer 24. 反转链表 #

## 题目介绍 ##

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

**示例：**

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

**限制：**

*  0 <= 节点个数 <= 5000

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

## 题目实现 ##

class Solution { 
        public ListNode reverseList(ListNode head) { 
            ListNode dummyHead = new ListNode();
            while (head != null) { 
                ListNode temp = head.next;
                head.next = dummyHead.next;
                dummyHead.next = head;
                head = temp;
            }
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

**示例1：**

输入：1->2->4, 1->3->4
    输出：1->1->2->3->4->4

**限制：**

*  0 <= 链表长度 <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            ListNode dummyHead = new ListNode();
            ListNode tail = dummyHead;
            while (l1 != null && l2 != null) { 
                if (l1.val <= l2.val) { 
                    tail = tail.next = l1;
                    l1 = l1.next;
                } else { 
                    tail = tail.next = l2;
                    l2 = l2.next;
                }
            }
            if (l1 != null) tail = tail.next = l1;
            if (l2 != null) tail = tail.next = l2;
            return dummyHead.next;
        }
    }

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

## 题目介绍 ##

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

**示例 1：**

![cdd80367654dc138d5323cea09461f30.png][]

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

**示例 2：**

![4ce3e916a187d9a7af8c645c102a3c9d.png][]

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

**示例 3：**

![b6114cfb00d7e9c96d13d601e3c55a90.png][]

输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

**示例 4：**

输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

**提示：**

*  \-10000 <= Node.val <= 10000
 *  Node.random 为空（null）或指向链表中的节点。
 *  节点数目不超过 1000 。

**相同题目：**

*  #### [138. 复制带随机指针的链表][138.] ####

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

## 题目实现 ##

我们遍历整个链表，在遍历的过程中，以 **旧节点** 为 **键** ，**新节点** 为 **值** 储存在哈希表中。

然后再次遍历整个链表，通过 **旧节点** 拿到 **新节点** ，然后为 **新节点** 进行 `next` 和 `random` 赋值即可。

class Solution { 
        public Node copyRandomList(Node head) { 
            if (head == null) return null;
            HashMap<Node, Node> hashMap = new HashMap<>();
            Node temp = head;
            while (temp != null) { 
                hashMap.put(temp, new Node(temp.val));
                temp = temp.next;
            }
            temp = head;
            while (temp != null) { 
                hashMap.get(temp).next = hashMap.get(temp.next);
                hashMap.get(temp).random = hashMap.get(temp.random);
                temp = temp.next;
            }
            return hashMap.get(head);
        }
    }
    ```# 面试题 02.03. 删除中间节点
    
    ## 题目介绍
    
    若链表中的某个节点，既不是链表头节点，也不是链表尾节点，则称其为该链表的「中间节点」。
    
    假定已知链表的某一个中间节点，请实现一种算法，将该节点从链表中删除。
    
    例如，传入节点 `c`（位于单向链表 `a->b->c->d->e->f` 中），将其删除后，剩余链表为 `a->b->d->e->f`
    
    **示例：**

输入：节点 5 （位于单向链表 4->5->1->9 中）  
输出：不返回任何数据，从链表中删除传入的节点 5，使链表变为 4->1->9

来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/delete-middle-node-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    
    ## 题目实现
    
    使用下一节点代替当前节点，以此达到删除的目的。
    
    ```java
    class Solution {
        public void deleteNode(ListNode node) {
            node.val = node.next.val;
            node.next = node.next.next;
        }
    }

# 面试题 02.08. 环路检测 #

## 题目介绍 ##

给定一个链表，如果它是有环链表，实现一个算法返回环路的开头节点。

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

**示例 1：**

![6b2cca89f34a78cac983b7983804e730.png][]

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

**示例 2：**

![cdf52ac475e6ff4c368a0e40e907d41e.png][]

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

**示例 3：**

![71737552109d837d0c1708c704f87f3c.png][]

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

**进阶：**

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

**用到题目：**

*  #### [141. 环形链表][141.] ####

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

## 题目实现 ##

class Solution { 
        public ListNode detectCycle(ListNode head) { 
            if (head == null) return null;
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) { 
                fast = fast.next.next;
                slow = slow.next;
                if (fast == slow) { 
                    // head 和 slow 下次相遇即为环起点
                    while (head != slow) { 
                        head = head.next;
                        slow = slow.next;
                    }
                    return slow;
                }
            }
            return null;
        }
    }

[d0dff411f5aa117923e76cd52df9c221.png]: /images/20221014/1c75272d0c0f45238a813439625ee514.png
[dccf83198c361ca1b10f6d9f705a6e6d.png]: /images/20221014/c5f59fd0de5d415bbd890c2639c25bc8.png
[4af3ffd1b08e70ce688a0987bc370e8b.png]: /images/20221014/8e7d64dc5b0c4a9e93cb036750b8c85b.png
[3a67d02d04b53c0132cbc6dd04cf2066.png]: /images/20221014/eaff7736e4ee4a7f8c1fe9b5ceb51f9f.png
[e294e891355d101c2ec7457654c26cdd.png]: /images/20221014/145b78391133425e9008511a1a674023.png
[Offer 35.]: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
[2c693f31894ccbcbb3cf116203bd2e76.png]: /images/20221014/b7822a7b25d84bf9a1232d2f2a6bf39c.png
[000233190926e2bc48c72b33dc5d7950.png]: /images/20221014/1a1a5c9cf78d465bb112c8bb92d84cc9.png
[39e0fc435ad7fdd1897b541828b5da7d.png]: /images/20221014/2265ee8bb3304a6196bcc86d4965e72e.png
[b878e97bd5d1a3b284fc451a9fdcbcfb.png]: /images/20221014/d794dd3bc36a46feb24a2f6803079194.png
[522917e96b6788cd2b02e0abe15c711a.png]: /images/20221014/495dd3e541a840bea79fac96b1b0c7dc.png
[c33319c83099c5212085641817077a71.png]: /images/20221014/703ce56c6bfb431d97152cbd4d33329c.png
[68cf2cc81187b5762bc819648be3f803.png]: /images/20221014/ebebdf9170f3473587249f6a99bb87b2.png
[58e61fdfa2a842d17d9a7895d32624d0.png]: /images/20221014/4309922d5a484b1a9771ca24cae68e3d.png
[6d84a7a4cd71785c24280c9be0248ce5.png]: /images/20221014/ba218b043ec44b3bb035dac98f959eca.png
[a2ebae794253c71cedf163d10f5ff19f.png]: /images/20221014/3058f0ba78d644a28570b7f3e5782cae.png
[7e2337a97e87e0872b189dd6f8c6f48c.png]: /images/20221014/19348b5874f34547be9eb59f7a386f97.png
[42fab0317e87fd4e667d349639bbb1a0.png]: /images/20221014/83676adf6aff40a08012d5c1be8035a2.png
[337df24355af0f2c8f4f8e9f2e94b556.png]: /images/20221014/736778563d2d42cd88843cd1ce74ca02.png
[f97e63af7cae4054c69a612dcce6c7ff.png]: /images/20221014/1c1fc4567db5447db1e62d7cfb0d109e.png
[02.07.]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/
[Offer 52.]: https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/
[b7b50c17bcaab25584099091144b6813.png]: /images/20221014/4c48eedd3d9e45d69e0db407e18c0c56.png
[25e7341bd60f5204859959138df5e8d6.png]: /images/20221014/c4a17186327d461ea51f5cf405068506.png
[c243036a8ff06695054a0bea2ba22996.png]: /images/20221014/d0146b0e5cb74520a6d7d8cef3b34906.png
[02.05.]: https://leetcode-cn.com/problems/sum-lists-lcci/
[2893cc7780a00288e0e7bed67c87d6a5.png]: /images/20221014/016af02bca5442709175cde1ee53f452.png
[Offer 18.]: https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/
[45556eed0262caf9c2c61c3ac75a2f8b.png]: /images/20221014/a214081532aa4082ab758588cead3bda.png
[dea5be6f67abed0bb28f0d63d9c323d6.png]: /images/20221014/6c13be8c47004b6d8fff9e854e1c5cad.png
[f4322e72ad8b47ab110d50a2e8d46a1b.png]: /images/20221014/f2d0659376e24a06bbf4b19a75237819.png
[ba58970738a37bb863bc7609d68d8982.png]: /images/20221014/71f581a7cfb74c6186564ed1b5cdb139.png
[d9ca4aa38feb2eb2d30a5deecd796793.png]: /images/20221014/86b6cabe731d4c5b9d682668c13ff6ac.png
[f2df6442a49e780cfa2859ee67cb6d38.png]: /images/20221014/2b4d93847cc94898b0a12f2a7588d1c2.png
[039b5bf72410768a2d16c54a0f4b0adb.png]: /images/20221014/09d77a0ba29c45b5a3901419ab36c113.png
[Offer 24.]: https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
[Offer II 024.]: https://leetcode-cn.com/problems/UHnkqh/
[c7b0c6667d82b95e7e6f6dbb326bc06c.png]: /images/20221014/26d41f64d448408284c7ef2ba7a53f5c.png
[c5fbfb28c081d307a6b924fb7485c627.png]: /images/20221014/4f5285f8b7b845f6b52423699fc4a7c9.png
[a03bac3016163e9b0bff2542107fbc33.png]: /images/20221014/3c2ec1d2c3e94b0d93c7b22fd041028e.png
[342659eed7ff98d8bf7beca0a26ae577.png]: /images/20221014/e29c879329d349da971e13c4f803c471.png
[1fafb784c2e5351c232f322e6f98e08e.png]: /images/20221014/b03efeb771454a449ff8adc303868af0.png
[Offer 25.]: https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
[286420205408102de04838ec912bae23.png]: /images/20221014/6a2746a5187e4e9f9e2c138fadb30368.png
[22eba2fe4cec6fbdd89ec7530db6cac9.png]: /images/20221014/779d35c7da5f4eaf9b6a52966cdcb9d4.png
[5fec0cde3f996ca5e872e40e9e171f66.png]: /images/20221014/2636fa7831ec455a9bc68ecaa68eea21.png
[0af2781e2457faf807a5759d7ad957e4.png]: /images/20221014/ae34d31d3e52414dbf40716b499fb052.png
[796382fc0032e19e3a0f9cfff9bf8147.png]: /images/20221014/9e452f9656a446c99369e207a908a261.png
[960d451ba8482e236ec6ee90497bccbb.png]: /images/20221014/38dc4870aba34d119998fa5490ae82f9.png
[64dc70cd46871063afd5411684949002.png]: /images/20221014/fcc93fc8015642be945157a210e4fb33.png
[7715ab287ccad4885b52a2d58f9d26fa.png]: /images/20221014/c4ebd89abbb44dab98c35fbe08f223ee.png
[895db150f648fb3be8a8278b17ba568d.png]: /images/20221014/f1295f6940d2496ea51a45836023cd5b.png
[902af78a571c1ff049250252755b4a22.png]: /images/20221014/2524895de3c7468aa7d317bf5e704acd.png
[21.]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[2b20937a09c2e8ac4db9120729e31f8b.png]: /images/20221014/eb2db79ba5da46b48bfd06e0cf9a6db2.png
[02.06.]: https://leetcode-cn.com/problems/palindrome-linked-list-lcci/
[206.]: https://leetcode-cn.com/problems/reverse-linked-list/
[876.]: https://leetcode-cn.com/problems/middle-of-the-linked-list/
[38ff2cb704fb5f302657a70c4d068b2f.png]: /images/20221014/35a793c7c6114ba3899a2921224726d7.png
[327258c0edc0fc5daf5c7fae8e651115.png]: /images/20221014/d50c1fbf048a46b8949c31f29248331f.png
[02.04.]: https://leetcode-cn.com/problems/partition-list-lcci/
[bad38b3e0b1e3ba7be457143ff225cf8.png]: /images/20221014/3938ea9b324f4311a892f9831c367efa.png
[22dee0aa354d948138e0a1deeb7da32d.png]: /images/20221014/fd1198cded88414dbd05e262763e09c2.png
[205d671709db39281e6c6d89224d1b17.png]: /images/20221014/3ec98edc34414f3ba227ee3c6e0023a0.png
[a43d7e4b764609cd1b3136a8410acc3d.png]: /images/20221014/318555291e1c4a3ca5db653ab92e355a.png
[3a0ae5d87b5fe2f09e68c23a67ff68ba.png]: /images/20221014/75263ff5656d48dcb829e895ece59fd9.png
[e855078e933bfae3b3521e1312bde05a.png]: /images/20221014/b229360d05364be9883519e2ae73c190.png
[b5539b6bc4c173da2bf0625b0fa71ec2.png]: /images/20221014/8a90e1176f604e66b2d1c9e82781b903.png
[7ec2af5b7667a59297dd0db7328aa68d.png]: /images/20221014/e38c52ae7cc04684a363b70f296c0fe9.png
[34da4f56034ef42c99994addf90f6987.png]: /images/20221014/fdf8ec3c4109436c8e70c1f4ea806efa.png
[75fe740429424f9ee47646c5e77327ec.png]: /images/20221014/566803f5df4542c7addfe29016ee6057.png
[5fee9e29bdc0b73a5d6152d4f6e0e5b2.png]: /images/20221014/6999bbcdd12746f6898fcac76f727d63.png
[2da642f8a2ba5ec9e765b966e8589d63.png]: /images/20221014/99ea141cadd54ab89b29416ac8ef61d2.png
[5137e59c16a142a0f9c14424ed0db6b0.png]: /images/20221014/edab586cbdbd4f8cb8198fae688c240a.png
[74350afa7274adc1592ae077fc9592b6.png]: /images/20221014/dd8f73bba6e64a009d9ddbf3e3e75ad9.png
[136e7ff929037fc035b8f8ee132500f6.png]: /images/20221014/ae3a6a1dcb034c6ba12b0adfa6e25c62.png
[b0527504fb6f01a42c4c7147e8400e71.png]: /images/20221014/e8cd775a5fdf4a4d87c94ca959bb0188.png
[cdd80367654dc138d5323cea09461f30.png]: /images/20221014/2f362cb513b141ae98e714178a241197.png
[4ce3e916a187d9a7af8c645c102a3c9d.png]: /images/20221014/d487872245084f0cabd13f92649a1ac2.png
[b6114cfb00d7e9c96d13d601e3c55a90.png]: /images/20221014/873e472490244715b73c4ba795620bdb.png
[138.]: https://leetcode-cn.com/problems/copy-list-with-random-pointer/
[6b2cca89f34a78cac983b7983804e730.png]: /images/20221014/504ee3180c7e482db9c379bbd83c0e13.png
[cdf52ac475e6ff4c368a0e40e907d41e.png]: /images/20221014/470a8f1fb0544444baf1b1e9f69f96b8.png
[71737552109d837d0c1708c704f87f3c.png]: /images/20221014/8b545fc41fdb47b78bfda081d4178f24.png
[141.]: https://leetcode-cn.com/problems/linked-list-cycle/