一、链表
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; // 头指针
@Override
public Iterator<Integer> iterator() {
// 匿名内部类 -> 带名字内部类
return new NodeIterator();
}
private class NodeIterator implements Iterator<Integer> {
Node p = head;
@Override
public boolean hasNext() { // 是否有下一个元素
return p != null;
}
@Override
public 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));
}
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
Node p = head.next;
@Override
public boolean hasNext() {
return p != tail;
}
@Override
public Integer next() {
int value = p.value;
p = p.next;
return value;
}
};
}
}
5. 环形链表（带哨兵）
双向环形链表带哨兵，这时哨兵既作为头，也作为尾
java实现：
public class DoublyLinkedListSentinel implements Iterable<Integer> {
@Override
public Iterator<Integer> iterator() {
return new Iterator<>() {
Node p = sentinel.next;
@Override
public boolean hasNext() {
return p != sentinel;
}
@Override
public 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;
}
}解法五：从链表每次拿到第二个节点，将其从链表断开，插入头部，直到它为null结束
- 设置指针o1(旧头)、n1(新头)、o2(旧老二)，分别指向第一、第一、第二节点
- 将o2节点从链表断开，即o1节点指向第三个节点
- o2节点链入链表头部
- n1指向o2
- o2指向o1的下一个节点
- 重复以上2~5步，直到o2指向null
- 还应考虑边界条件，即链表中不满两个元素时，无需走以上逻辑
public ListNode reverseList(ListNode o1) {
if (o1 == null || o1.next == null) { // 不足两个节点
return o1;
}
ListNode o2 = o1.next;
ListNode n1 = o1;
while (o2 != null) {
o1.next = o2.next;
o2.next = n1;
n1 = o2;
o2 = o1.next;
}
return n1;
}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 <= 500 <= 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 <= 300 <= Node.val <= 1001 <= 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 <= 100l1和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.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[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^5pos为-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 <= 105pos的值为-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 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal- 相交的起始节点的值。如果不存在相交节点，这一值为0listA- 第一个链表listB- 第二个链表skipA- 在listA中（从头节点开始）跳到交叉节点的节点数skipB- 在listB中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
示例 1：
输入：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 中第四个节点) 在内存中指向相同的位置。
示例 2：
输入：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 个节点。
示例 3：
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。
提示：
listA中节点数目为mlistB中节点数目为n1 <= m, n <= 3 * 1041 <= Node.val <= 1050 <= skipA <= m0 <= skipB <= n- 如果
listA和listB没有交点，intersectVal为0 - 如果
listA和listB有交点，intersectVal == listA[skipA] == listB[skipB]
进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
解法一：遍历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;
}
}
}
}