数据结构与算法 - 链表

一、链表

1. 概述

定义：在计算机科学中，链表是数据元素的线性集合，其每个元素都指向下一个元素，元素存储上并不连续。

可以分类为：

单向链表，每个元素只知道其下一个元素是谁

双向链表，每个元素直到其上一个元素和下一个元素

循环链表，通常的链表尾节点tail指向的都是null，而循环链表的tail指向的是头节点head

链表内还有一种特殊的节点称为哨兵（Sentinel）节点，也叫做哑元（Dummy）节点，它不存储数据，通常用作头尾，用来简化边界判断，如下图所示

随机访问性能

根据index查找，时间复杂度O(n)

插入或删除性能

• 起始位置：O(1)
• 结束位置：如果已知tail尾节点是O(1)，不知道tail尾节点是O(n)
• 中间位置：根据index查找时间 + O(1)

2. 单向链表

根据单向链表的定义，首先定义一个存储value和next指针的类Node，和一个描述头部节点的引用

public class SinglyLinkedList {private Node head; // 头部节点private static class Node { // 节点类int value;Node next;public Node(int value, Node next) {this.value = value;this.next = next;}}
}

• Node定义为内部类，是为了对外隐藏实现细节，没必要让类的使用者关系Node结构
• 定义为static内部类，是因为Node不需要与SinglyLinkedList实例相关，多个SinglyLinkedList实例能共用Node类定义

头部添加（头插法）

public class SinglyLinkedList {// ...public void addFirst(int value) {this.head = new Node(value, this.head);}
}

如果this.head == null，新增节点指向null，并作为新的this.head

如果this.head != null，新增节点指向原来的this.head，并作为新的this.head。注意赋值操作执行顺序是从右到左。

while遍历

public class SinglyLinkedList {// ...public void loop(Consumer<Integer> consumer) {Node curr = this.head;while (curr != null) {// 做一些事consumer.accept(curr.value);curr = curr.next;}}
}

for遍历

public class SinglyLinkedList {// ...public void loop() {for (Node curr = this.head; curr != null; curr = curr.next) {// 做一些事}}
}

以上两种遍历都可以把要做的事情以Consumer函数的方式传递过来

• Consumer的规则是一个参数，无返回值，因此像System.out.println方法等都是Consumer
• 调用Consumer时，将当前节点curr.value作为参数传递给它

迭代器遍历

public class SinglyLinkedList implements Iterable<Integer> {// ...private class NodeIterator implements Iterator<Integer> {Node curr = head;public boolean hasNext() {return curr != null;}public Integer next() {int value = curr.value;curr = curr.next;return value;}}public Iterator<Integer> iterator() {return new NodeIterator();}
}

• hasNext用来判断是否还有必要调用next
• next做两件事：①返回当前节点的value；②指向下一个节点
• NodeIterator要定义为非static内部类，是因为它与SinglyLinkedList实例相关，是对某个SinglyLinkedList实例的迭代

递归遍历

public class SinglyLinkedList implements Iterable<Integer> {// ...public void loop(Consumer<Integer> before, Consumer<Integer> after) {recursion(this.head, before, after);}private void recursion(Node curr, Consumer<Integer> before, Consumer<Integer> after) {if (curr == null) {return;}// 前面做些事before.accept(curr.value);recursion(curr.next, before, after);// 后面做些事after.accept(curr.value);}
}

尾部添加（尾插法）

public class SinglyLinkedList {// ...private Node findLast() {if (this.head == null) {return null;}Node curr;for (curr = this.head; curr.next != null; ) {curr = curr.next;}return curr;}public void addLast(int value) {Node last = findLast();if (last == null) {addFirst(value);return;}last.next = new Node(value, null);}
}

注意，找最后一个节点，终止条件是curr.next == null

尾部添加多个

public class SinglyLinkedList {// ...public void addLast(int first, int... rest) {Node sublist = new Node(first, null);Node curr = sublist;for (int value : rest) {curr.next = new Node(value, null);curr = curr.next;}Node last = findLast();if (last == null) {this.head = sublist;return;}last.next = sublist;}
}

先串成一串sublist，再作为一个整体添加

根据索引获取

public class SinglyLinkedList {// ...private Node findNode(int index) {int i = 0;for (Node curr = this.head; curr != null; curr = curr.next, i++) {if (index == i) {return curr;}}return null;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}public int get(int index) {Node node = findNode(index);if (node != null) {return node.value;}throw illegalIndex(index);}
}

插入

public class SinglyLinkedList {// ...public void insert(int index, int value) {if (index == 0) {addFirst(value);return;}Node prev = findNode(index - 1); // 找到上一个节点if (prev == null) { // 找不到throw illegalIndex(index);}prev.next = new Node(value, prev.next);}
}

• 插入包括下面的删除，都必须先找到上一个节点

删除

public class SinglyLinkedList {// ...public void remove(int index) {if (index == 0) {if (this.head != null) {this.head = this.head.next;return;} else {throw illegalIndex(index);}}Node prev = findNode(index - 1);Node curr;if (prev != null && (curr = prev.next) != null) {prev.next = curr.next;} else {throw illegalIndex(index);}}
}

• 第一个if块对应着removeFirst情况
• 最后一个if块对应着至少两个节点的情况，不仅仅判断上一个节点非空，还要保证当前节点非空

完整代码：

package com.itheima.datastructure.linkedlist;import java.util.Iterator;
import java.util.function.Consumer;/*** 单向链表*/
public class SinglyLinkedList implements Iterable<Integer> { // 整体private Node head = null; // 头指针@Overridepublic Iterator<Integer> iterator() {// 匿名内部类 -> 带名字内部类return new NodeIterator();}private class NodeIterator implements Iterator<Integer> {Node p = head;@Overridepublic boolean hasNext() { // 是否有下一个元素return p != null;}@Overridepublic Integer next() { // 返回当前值, 并指向下一个元素int v = p.value;p = p.next;return v;}}/*** 节点类*/private static class Node {int value; // 值Node next; // 下一个节点指针public Node(int value, Node next) {this.value = value;this.next = next;}}/*** 向链表头部添加** @param value 待添加值*/public void addFirst(int value) {// 1. 链表为空
//        head = new Node(value, null);// 2. 链表非空head = new Node(value, head);}/*** 遍历链表1** @param consumer 要执行的操作*/public void loop1(Consumer<Integer> consumer) {Node p = head;while (p != null) {consumer.accept(p.value);p = p.next;}}/*** 遍历链表2** @param consumer 要执行的操作*/public void loop2(Consumer<Integer> consumer) {for (Node p = head; p != null; p = p.next) {consumer.accept(p.value);}}public void loop3(Consumer<Integer> before,Consumer<Integer> after) {recursion(head, before, after);}private void recursion(Node curr,Consumer<Integer> before, Consumer<Integer> after) { // 某个节点要进行的操作if (curr == null) {return;}before.accept(curr.value);recursion(curr.next, before, after);after.accept(curr.value);}private Node findLast() {if (head == null) { // 空链表return null;}Node p;for (p = head; p.next != null; p = p.next) {}return p;}/*** 向链表尾部添加** @param value 待添加值*/public void addLast(int value) {Node last = findLast();if (last == null) { // 空链表addFirst(value);return;}last.next = new Node(value, null);}private Node findNode(int index) {int i = 0;for (Node p = head; p != null; p = p.next, i++) {if (i == index) {return p;}}return null; // 没找到}/*** 根据索引查找** @param index 索引* @return 找到, 返回该索引位置节点的值* @throws IllegalArgumentException 找不到, 抛出 index 非法异常*/public int get(int index) throws IllegalArgumentException {Node node = findNode(index);if (node == null) {throw illegalIndex(index);}return node.value;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}/*** 向索引位置插入** @param index 索引* @param value 待插入值* @throws IllegalArgumentException 找不到, 抛出 index 非法异常*/public void insert(int index, int value) throws IllegalArgumentException {if (index == 0) {addFirst(value);return;}Node prev = findNode(index - 1); // 找到上一个节点if (prev == null) { // 找不到throw illegalIndex(index);}prev.next = new Node(value, prev.next);}/*** 删除第一个** @throws IllegalArgumentException - 如果不存在, 抛出 index 非法异常*/public void removeFirst() throws IllegalArgumentException {if (head == null) {throw illegalIndex(0);}head = head.next;}/*** 从索引位置删除** @param index 索引* @throws IllegalArgumentException 找不到, 抛出 index 非法异常*/public void remove(int index) throws IllegalArgumentException {if (index == 0) {removeFirst();return;}Node prev = findNode(index - 1); // 上一个节点if (prev == null) {throw illegalIndex(index);}Node removed = prev.next; // 被删除的节点if (removed == null) {throw illegalIndex(index);}prev.next = removed.next;}
}

3. 单向链表（带哨兵）

观察之前单向链表的实现，发现每个方法内几乎都有判断是不是head这样的代码，能不能简化呢？

用一个不参与数据存储的特殊Node作为哨兵，它一般被称为哨兵或哑元，拥有哨兵节点的链表称为带头链表。

public class SinglyLinkedListSentinel {// ...private Node head = new Node(Integer.MIN_VALUE, null);
}

• 具体存什么值无所谓，因为不会用到它的值

加入哨兵节点后，代码会变得比较简单，先看几个工具方法

public class SinglyLinkedListSentinel {// ...// 根据索引获取节点private Node findNode(int index) {int i = -1;for (Node curr = this.head; curr != null; curr = curr.next, i++) {if (i == index) {return curr;}}return null;}// 获取最后一个节点private Node findLast() {Node curr;for (curr = this.head; curr.next != null; ) {curr = curr.next;}return curr;}
}

• findNode与之前类似，只是i初始值设置为-1对应哨兵，实际传入的index也是[-1, infty]
• findLast绝不会返回null了，就算没有其他节点，也会返回哨兵作为最后一个节点

代码简化为：

public class SinglyLinkedListSentinel {// ...public void addLast(int value) {Node last = findLast();/*改动前if (last == null) {this.head = new Node(value, null);return;}*/last.next = new Node(value, null);}public void insert(int index, int value) {/*改动前if (index == 0) {this.head = new Node(value, this.head);return;}*/// index 传入 0 时，返回的是哨兵Node prev = findNode(index - 1);if (prev != null) {prev.next = new Node(value, prev.next);} else {throw illegalIndex(index);}}public void remove(int index) {/*改动前if (index == 0) {if (this.head != null) {this.head = this.head.next;return;} else {throw illegalIndex(index);}}*/// index 传入 0 时，返回的是哨兵Node prev = findNode(index - 1);Node curr;if (prev != null && (curr = prev.next) != null) {prev.next = curr.next;} else {throw illegalIndex(index);}}public void addFirst(int value) {/*改动前this.head = new Node(value, this.head);*/this.head.next = new Node(value, this.head.next);// 也可以视为 insert 的特例, 即 insert(0, value);}
}

对于删除，前面说了【最后一个if块对应着至少得两个节点的情况】，现在由零哨兵，就凑足了两个节点。

4. 双向链表（带哨兵）

package com.itheima.datastructure.linkedlist;import java.util.Iterator;/*** 双向链表(带哨兵)*/
public class DoublyLinkedListSentinel implements Iterable<Integer> {static class Node {Node prev; // 上一个节点指针int value; // 值Node next; // 下一个节点指针public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}private Node head; // 头哨兵private Node tail; // 尾哨兵public DoublyLinkedListSentinel() {head = new Node(null, 666, null);tail = new Node(null, 888, null);head.next = tail;tail.prev = head;}Node findNode(int index) {int i = -1;for (Node p = head; p != tail; p = p.next, i++) {if (i == index) {return p;}}return null;}public void addFirst(int value) {insert(0, value);}public void removeFirst() {remove(0);}public void addLast(int value) {Node last = tail.prev;Node added = new Node(last, value, tail);last.next = added;tail.prev = added;}public void removeLast() {Node removed = tail.prev;if (removed == head) {throw illegalIndex(0);}Node prev = removed.prev;prev.next = tail;tail.prev = prev;}public void insert(int index, int value) {Node prev = findNode(index - 1);if (prev == null) {throw illegalIndex(index);}Node next = prev.next;Node inserted = new Node(prev, value, next);prev.next = inserted;next.prev = inserted;}public void remove(int index) {Node prev = findNode(index - 1);if (prev == null) {throw illegalIndex(index);}Node removed = prev.next;if (removed == tail) {throw illegalIndex(index);}Node next = removed.next;prev.next = next;next.prev = prev;}private IllegalArgumentException illegalIndex(int index) {return new IllegalArgumentException(String.format("index [%d] 不合法%n", index));}@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {Node p = head.next;@Overridepublic boolean hasNext() {return p != tail;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}
}

5. 环形链表（带哨兵）

双向环形链表带哨兵，这时哨兵既作为头，也作为尾

java实现：

public class DoublyLinkedListSentinel implements Iterable<Integer> {@Overridepublic Iterator<Integer> iterator() {return new Iterator<>() {Node p = sentinel.next;@Overridepublic boolean hasNext() {return p != sentinel;}@Overridepublic Integer next() {int value = p.value;p = p.next;return value;}};}static class Node {Node prev;int value;Node next;public Node(Node prev, int value, Node next) {this.prev = prev;this.value = value;this.next = next;}}private final Node sentinel = new Node(null, -1, null); // 哨兵public DoublyLinkedListSentinel() {sentinel.next = sentinel;sentinel.prev = sentinel;}/*** 添加到第一个* @param value 待添加值*/public void addFirst(int value) {Node next = sentinel.next;Node prev = sentinel;Node added = new Node(prev, value, next);prev.next = added;next.prev = added;}/*** 添加到最后一个* @param value 待添加值*/public void addLast(int value) {Node prev = sentinel.prev;Node next = sentinel;Node added = new Node(prev, value, next);prev.next = added;next.prev = added;}/*** 删除第一个*/public void removeFirst() {Node removed = sentinel.next;if (removed == sentinel) {throw new IllegalArgumentException("非法");}Node a = sentinel;Node b = removed.next;a.next = b;b.prev = a;}/*** 删除最后一个*/public void removeLast() {Node removed = sentinel.prev;if (removed == sentinel) {throw new IllegalArgumentException("非法");}Node a = removed.prev;Node b = sentinel;a.next = b;b.prev = a;}/*** 根据值删除节点* <p>假定 value 在链表中作为 key, 有唯一性</p>* @param value 待删除值*/public void removeByValue(int value) {Node removed = findNodeByValue(value);if (removed != null) {Node prev = removed.prev;Node next = removed.next;prev.next = next;next.prev = prev;}}private Node findNodeByValue(int value) {Node p = sentinel.next;while (p != sentinel) {if (p.value == value) {return p;}p = p.next;}return null;}}

6. 习题

6.1 反转单向链表

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解法一：构建一个新链表，从旧链表依次拿到每个节点，创建新结点添加至新链表头部，完成后新链表既是倒序的（头插法）

/*** 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 reverseList(ListNode head) {ListNode n1 = null;ListNode p = head;while(p != null) {n1 = new ListNode(p.val, n1);p = p.next;}return n1;}
}

解法二：与解法一类似，构造一个新链表，从旧链表头部移除节点，添加到新链表头部，完成后新链表是倒序的，区别在于原题目并未提供节点外层的容器类，这里提供一个，另外一个区别就是并不去构造新结点。

/*** 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 {static class List {ListNode head;public List(ListNode head) {this.head = head;}public ListNode removeFirst() {ListNode first = head;if (first != null) {head = head.next;}return first;}public void addFirst(ListNode first) {first.next = head;head = first;}}public ListNode reverseList(ListNode head) {List list1 = new List(head);List list2 = new List(null);ListNode first;while ((first = list1.removeFirst()) != null) {list2.addFirst(first);}return list2.head;}
}

解法三：递归

/*** 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 reverseList(ListNode head) {if(head == null || head.next == null) {return head;}ListNode reversedHead = reverseList(head.next);head.next.next = head;head.next = null;return reversedHead;}
}

解法四：迭代。遍历链表，同时逐步改变每个节点的指向，使它们反向指向前一个结点，而不需要额外的空间来存储节点。

时间复杂度：O(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 reverseList(ListNode head) {ListNode prev = null;ListNode curr = head;while (curr != null) {ListNode nextTmp = curr.next;  // 先保存当前节点的下一个节点curr.next = prev;  // 将当前节点指向它的前一个节点prev = curr;  // 移动prev指向当前节点，成为接下来节点的前一节点curr = nextTmp;  // 继续向后遍历链表}return prev;}
}

6.2 移除链表元素

给你一个链表的头节点 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

解法一：

/*** 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 null;}if(head.val == val) {// 跳过当前节点并递归删除后面的节点return removeElements(head.next, val);} else {// 保留当前节点并连接其后的结果head.next = removeElements(head.next, val);return head;}}
}

6.3 删除链表的倒数第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

解法一：快慢指针法。fast先走n + 1步，slow指向待删节点的上一个节点

/*** 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(-1, head);ListNode fast = dummy;ListNode slow = dummy;for(int i = 0; i < n + 1; i++) {fast = fast.next;}while(fast != null) {fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

解法二：

/*** 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 recursion(ListNode p, int n) {if(p == null) {return 0;}// 向下深入到链表的末尾，并等候返回值nth// nth代表当前节点的深度（距离链表末尾的节点数）int nth = recursion(p.next, n);if(nth == n) {// 当前节点是倒数第N个节点的前一个结点p.next = p.next.next;}// 增加一层深度的计数，以便在递归调用过程中可以准确地判断出节点的位置return nth + 1;}public ListNode removeNthFromEnd(ListNode head, int n) {ListNode sentinel = new ListNode(-1, head);recursion(sentinel, n);return sentinel.next;}
}

6.4 删除排序链表中的重复元素

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

示例 1：

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

示例 2：

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

提示：

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

解法一：迭代

/*** 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) {ListNode curr = head;while(curr != null && curr.next != null) {if(curr.val == curr.next.val) {curr.next = curr.next.next;} else {curr = curr.next;}}return head;}
}

解法二：递归

/*** 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;}if(head.val == head.next.val) {return deleteDuplicates(head.next);} else {// 保留当前节点，并递归后续节点head.next = deleteDuplicates(head.next);return head;}}
}

6.5 删除排序链表中的重复元素Ⅱ

给定一个已排序的链表的头 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
• 题目数据保证链表已经按升序 排列

解法一：递归函数负责返回：从当前节点（我）开始，完成去重的链表

• 若我与next重复，一直找到下一个不重复的节点，以它的返回结果为准
• 若我与next不重复，返回我，同时更新next

/*** 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;}if(head.val == head.next.val) {// 如果当前节点与next重复，一直找到下一个不重复的节点ListNode x = head.next.next;while(x != null && x.val == head.val) {x = x.next;}return deleteDuplicates(x);} else {// 保留当前节点，并从下一个节点开始递归head.next = deleteDuplicates(head.next);return head;}}
}

6.6 合并两个有序链表

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

示例 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 均按 非递减顺序 排列

解法一：递归。递归函数应该返回

• 更小的那个链表节点，并把它剩余节点与另一个链表再次递归
• 返回之前，更新此节点的next

/*** 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 list1, ListNode list2) {if(list1 == null) {return list2;}if(list2 == null) {return list1;}if(list1.val < list2.val) {list1.next = mergeTwoLists(list1.next, list2);return list1;} else {list2.next = mergeTwoLists(list1, list2.next);return list2;}}
}

解法二：

/*** 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 list1, ListNode list2) {ListNode s = new ListNode(-1, null);ListNode p = s;while(list1 != null && list2 != null) {// 谁小把谁链给p，p和小的都向后平移一位if(list1.val < list2.val) {p.next = list1;list1 = list1.next;} else {p.next = list2;list2 = list2.next;}p = p.next;}// 处理剩余节点if(list1 != null) {p.next = list1;}if(list2 != null) {p.next = list2;}return s.next;}
}

6.7 合并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

解法一：递归

/*** 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 list1, ListNode list2) {ListNode s = new ListNode(-1, null);ListNode p = s;while (list1 != null && list2 != null) {// 谁小把谁链给p，p和小的都向后平移一位if (list1.val < list2.val) {p.next = list1;list1 = list1.next;} else {p.next = list2;list2 = list2.next;}p = p.next;}// 处理剩余节点if (list1 != null) {p.next = list1;}if (list2 != null) {p.next = list2;}return s.next;}// 这个方法采用了递归的方法，将 lists 数组中的链表进行二分合并public ListNode split(ListNode[] lists, int i, int j) {if (j == i) {return lists[i];}int m = (i + j) >>> 1;return mergeTwoLists(split(lists, i, m), split(lists, m + 1, j));}public ListNode mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}return split(lists, 0, lists.length - 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 mergeKLists(ListNode[] lists) {if (lists.length == 0) {return null;}// 优先队列根据ListNode的值自动排序PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);// 将所有非空链表的头节点添加到优先队列中for(ListNode list : lists) {if(list != null) {pq.offer(list);}}// 创建哨兵节点简化合并链表的操作ListNode dummy = new ListNode(-1);ListNode tail = dummy;// 当优先队列不为空时，进行合并操作while(!pq.isEmpty()) {ListNode node = pq.poll();  // 取出最小的节点tail.next = node;  // 将返回的节点连接到合并链表中tail = tail.next;  // 移动尾指针// 如果当前节点存在下一个节点，添加到优先队列中if(node.next != null) {pq.offer(node.next);}}return dummy.next;}
}

6.8 链表的中间节点

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

提示：

• 链表的结点数范围是 [1, 100]
• 1 <= Node.val <= 100

解法一：快慢指针法

/*** 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) {ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}
}

6.9 回文链表

给你一个单链表的头节点 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) 空间复杂度解决此题？

解法一：先找到链表中间节点，然后反转后半部分链表，比较前后两半链表值是否相等

/*** 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 {// 利用快慢指针法寻找中间节点private ListNode middle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}// 反转后半个链表private ListNode reverse(ListNode head) {ListNode curr = null;while(head != null) {ListNode tmp = head.next;head.next = curr;curr = head;head = tmp;}return curr;}public boolean isPalindrome(ListNode head) {ListNode middle = middle(head);ListNode newHead = reverse(middle);// 将反转后链表与原链表比较while(newHead != null) {if(newHead.val != head.val) {return false;}newHead = newHead.next;head = head.next;}return true;}
}

解法二：优化

/*** 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;}ListNode slow = head;  // 慢指针ListNode fast = head;  // 快指针ListNode newHead = null;  // 新头ListNode oldHead = head;  // 旧头// 快慢指针找中间点while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;// 反转前半部分oldHead.next = newHead;newHead = oldHead;oldHead = slow;}// 节点数为奇数if(fast != null) {slow = slow.next;}// 同步比较新头和后半部分while(newHead != null) {if(newHead.val != slow.val) {return false;}slow = slow.next;newHead = newHead.next;}return true;}
}

6.10 环形链表

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：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, 10^4]
• -10^5 <= Node.val <= 10^5
• pos 为 -1 或者链表中的一个 有效索引 。

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

/*** 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) {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;}
}

6.11 环形链表Ⅱ

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

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：你是否可以使用 O(1) 空间解决此题？

解题思路：如果链表上存在环，那么在环上以不同速度前进的两个指针必定会在某个时刻相遇。算法分为两个阶段

阶段1

• 龟一次走一步，兔子一次走两步

• 当兔子能走到终点时，不存在环

• 当兔子能追上龟时，可以判断存在环

阶段2

• 从它们第一次相遇开始，龟回到起点，兔子保持原位不变

• 龟和兔子一次都走一步

• 当再次相遇时，地点就是环的入口

为什么呢？

• 设起点到入口走 a 步，绕环一圈长度为 b，

• 那么从起点开始，走 a + 绕环 n 圈，都能找到环入口

• 第一次相遇时

  • 兔走了 a + 绕环 n 圈 + k，k 是它们相遇距环入口位置

  • 龟走了 a + 绕环 n 圈 + k，当然它绕的圈数比兔少

  • 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈

• 而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口

解法一：

/*** 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) {if(head == null || head.next == null) {return null;}ListNode slow = head;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if(slow == fast) {ListNode slow2 = head;// 找到环的入口while(slow2 != slow) {slow = slow.next;slow2 = slow2.next;}return slow;}}return null;}
}

6.12 删除链表中的节点

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

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

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

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

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

自定义测试：

• 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
• 我们将构建链表，并将节点传递给你的函数。
• 输出将是调用你函数后的整个链表。

示例 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

提示：

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

解法一：把下一个节点赋值给待删除节点，把下一个节点删除

/*** 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;  // 把下一个节点删除}
}

6.13 相交链表

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

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

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

解法一：遍历a，遇到null时改道遍历b。遍历b，遇到null时改道遍历a

/*** 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 p1 = headA;ListNode p2 = headB;while(true) {if(p1 == p2) {return p1;}if(p1 == null) {p1 = headB;} else {p1 = p1.next;}if(p2 == null) {p2 = headA;} else {p2 = p2.next;}}}
}