一.认识链表

1.链表定义与分类

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

可以分类为.

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

• 双向链表，每个元素知道其上一个元素和下一个元素

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

2.哨兵节点

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

3.查询性能

随机访问性能

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

4.插入和删除性能

插入或删除性能

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

二.单向链表

1.定义

根据单向链表的定义，首先定义一个存储 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 类定义

2.头部添加

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
  • 注意赋值操作执行顺序是从右到左

3.while 遍历

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

4.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 作为参数传递给它

//使用Consumer传参
public void loop4(Consumer<Integer> consumer) {
    Node p = head;
    while (p != null) {
        consumer.accept(p.value);
        p = p.next;
    }
}

//测试
@Test
@DisplayName("测试 consumer while遍历 loop4")
public void test5() {
    SinglyLinkedList list = new SinglyLinkedList();
    list.addFirst(1);
    list.addFirst(2);
    list.addFirst(3);
    list.addFirst(4);
    Consumer<Integer> consumer = integer -> System.out.println(integer);
    list.loop4(consumer);
}

5.迭代器遍历

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 实例的迭代

6.递归遍历

public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    public void loop() {
        recursion(this.head);
    }

    private void recursion(Node curr) {
        if (curr == null) {
            return;
        }
        //前面做些事
        recursion(curr.next);
        //后面做些事
    }
}

7.尾部添加

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
• 分成两个方法是为了代码清晰，而且 findLast() 之后还能复用

8.尾部添加多个

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
• 再作为一个整体添加

9.根据索引获取

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);
    }
}

• 同样，分方法可以实现复用

10.插入

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);
    }
}

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

11.删除

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 块对应着至少得两个节点的情况
  • 不仅仅判断上一个节点非空，还要保证当前节点非空

三.单向链表（带哨兵）

1.带哨兵单向链表

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

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

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

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

2.获取索引节点

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

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 了，就算没有其它节点，也会返回哨兵作为最后一个节点

3.插入删除节点

这样，代码简化为

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 块对应着至少得两个节点的情况】，现在有了哨兵，就凑足了两个节点

四.双向链表（带哨兵）

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    private final Node head;
    private final Node tail;

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
        head.next = tail;
        tail.prev = head;
    }

    private 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 prev = tail.prev;
        Node added = new Node(prev, value, tail);
        prev.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;
            }
        };
    }

    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;
        }
    }
}

五.环形链表（带哨兵）

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

参考实现

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;
    }

}

六.解题模版

1.反转链表再正向遍历

可以先将链表反转，然后正向遍历即可实现从后往前遍历。这种方法的时间复杂度为 O(N)，其中 N 为链表的长度。

CLASS LISTNODE:
    DEF __INIT__(SELF, VAL=0, NEXT=NONE):
        SELF.VAL = VAL
        SELF.NEXT = NEXT
DEF REVERSELIST(HEAD):
    PREV, CURR = NONE, HEAD
    WHILE CURR:
        NEXT_NODE = CURR.NEXT
        CURR.NEXT = PREV
        PREV = CURR
        CURR = NEXT_NODE
    RETURN PREV

DEF TRAVERSELIST(HEAD):
    NEW_HEAD = REVERSELIST(HEAD)
    WHILE NEW_HEAD:
        PRINT(NEW_HEAD.VAL)
        NEW_HEAD = NEW_HEAD.NEXT

2.递归遍历

可以使用递归的方式遍历链表，每次遍历到链表末尾时再开始输出节点的值。这种方法的时间复杂度也为 O(N)，其中 N 为链表的长度。

CLASS LISTNODE:
    DEF __INIT__(SELF, VAL=0, NEXT=NONE):
        SELF.VAL = VAL
        SELF.NEXT = NEXT

DEF TRAVERSELIST(HEAD):
    IF NOT HEAD:
        RETURN
    TRAVERSELIST(HEAD.NEXT)
    PRINT(HEAD.VAL)

需要注意的是，递归遍历链表时，如果链表过长，可能会导致递归层数过深，从而出现栈溢出的情况。因此，如果链表长度较大，建议使用反转链表再正向遍历的方法。

七.链表题目

2.移除链表元素-力扣 203 题

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

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

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

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

1.解法一

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        """
        链表的合适是操作2个节点,前驱和后继
        :param head:
        :param val:
        :return:
        """
        # 处理头部节点
        while head and head.val == val:
            head = head.next
        # 处理非头部
        cur = head
        while cur and cur.next:
            if cur.next.val == val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head

2.解法二

图中 s 代表 sentinel 哨兵（如果不加哨兵，则删除第一个节点要特殊处理），例如要删除 6

p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• 如果 p2 不等于目标，则 p1，p2 不断后移

	 p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

	 	  p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• p2 == 6，删除它，注意 p1 此时保持不变，p2 后移

	 	  p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 不等于目标，则 p1，p2 不断后移

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 == 6，删除它，注意 p1 此时保持不变，p2 后移

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> null

• p2 == null 退出循环

迭代法:

/**
 * 方法1 迭代法
 *
 * @param head 链表头
 * @param val  目标值
 * @return 删除后的链表头
 */
public ListNode removeElements(ListNode head, int val) {
    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2 = p1.next;
    while (p2 != null) {
        if (p2.val == val) {
            p1.next = p2.next;
            p2 = p2.next;
        } else {
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    return s.next;
}

3.解法三

递归法:

思路，递归函数负责返回：从当前节点（我）开始，完成删除的子链表

1. 若我与 v 相等，应该返回下一个节点递归结果
2. 若我与 v 不等，应该返回我，但我的 next 应该更新（让我能带上后续删过的子链表）

removeElements(ListNode p=1, int v=6){
    1.next=removeElements(ListNode p=2, int v=6){
    	2.next=removeElements(ListNode p=6, int v=6){
    		removeElements(ListNode p=3, int v=6){
    			3.next=removeElements(ListNode p=6, int v=6){
    				removeElements(ListNode p=null, int v=6){
    					// 没有节点,返回
                        return null
					}
				}
                return 3
			}
		}
        return 2
    }
    return 1
}

/**
 * 方法2  递归法
 *
 * @param p   链表头
 * @param val 目标值
 * @return 删除后的链表头
 */
public ListNode removeElements(ListNode p, int val) {
    if (p == null) {
        return null;
    }
    if (p.val == val) {
        return removeElements(p.next, val);
    } else {
        p.next = removeElements(p.next, val);
        return p;
    }
}

3.删除倒数节点-力扣 19 题

例如

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

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

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

另外题目提示

• 链表至少一个节点
• n 只会在合理范围

1.解法一

思路，写一个递归函数，用来返回下一个节点的倒数序号

recursion(ListNode p=1, int n=2) {
    recursion(ListNode p=2, int n=2) {
    	recursion(ListNode p=3, int n=2) {
    		recursion(ListNode p=4, int n=2) {
    			recursion(ListNode p=5, int n=2) {
    				recursion(ListNode p=null, int n=2) {
    					return 0; // 最内层序号0
					}
                    return 1; // 上一次返回值+1
				}
                return 2;
			}
            if(返回值 == n == 2) {
                // 删除 next
            }
            return 3;
		}
        return 4;
	}
    return 5;
}

但上述代码有一个问题，就是若删除的是第一个节点，它没有上一个节点，因此可以加一个哨兵来解决

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode sentinel = new ListNode(-1, head);
    recursion(sentinel, n);
    return sentinel.next;
}

public int recursion(ListNode p, int n) {
    if (p == null) {
        return 0;
    }
    int nth = recursion(p.next, n);
    if (nth == n) {
        p.next = p.next.next;
    }
    return nth + 1;
}

Q：p.next.next 不怕空指针吗？

A：

• p 是待删除节点的上一个节点，如果能递归回到 p，那么 p.next 肯定有值，不会是 null
• 且题目说明了 n >=1，不会因为 nth == 0 而让 p.next 指向最后的 null

2.解法二

快慢指针，p1 指向待删节点的上一个，p2 先走 n + 1 步

i=0
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

     i=1
     p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

          i=2
          p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               i=3 从此开始 p1 p2 依次向右平移, 直到 p2 移动到末尾
p1             p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               p1             p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

代码

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2 = s;
    for (int i = 0; i < n + 1; i++) {
        p2 = p2.next;
    }
    while (p2 != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    p1.next = p1.next.next;
    return s.next;
}

4.有序链表去重-力扣 83 题

例如

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

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

注意：重复元素保留一个

1.解法一

p1   p2
1 -> 1 -> 2 -> 3 -> 3 -> null

• p1.val == p2.val 那么删除 p2，注意 p1 此时保持不变

p1   p2
1 -> 2 -> 3 -> 3 -> null

• p1.val != p2.val 那么 p1，p2 向后移动

     p1   p2
1 -> 2 -> 3 -> 3 -> null

          p1   p2
1 -> 2 -> 3 -> 3 -> null

• p1.val == p2.val 那么删除 p2

          p1   p2
1 -> 2 -> 3 -> null

• 当 p2 == null 退出循环

代码

public ListNode deleteDuplicates(ListNode head) {
    // 链表节点 < 2
    if (head == null || head.next == null) {
        return head;
    }
    // 链表节点 >= 2
    ListNode p1 = head;
    ListNode p2;
    while ((p2 = p1.next) != null) {
        if (p1.val == p2.val) {
          	//跳过重复的元素,但是保留了p1的第一个值
            p1.next = p2.next;
        } else {
            p1 = p1.next;
        }
    }
    return head;
}

2.解法二

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

1. 若我与 next 重复，返回 next
2. 若我与 next 不重复，返回我，但 next 应当更新

deleteDuplicates(ListNode p=1) {
    deleteDuplicates(ListNode p=1) {
        1.next=deleteDuplicates(ListNode p=2) {
            2.next=deleteDuplicates(ListNode p=3) {
                deleteDuplicates(ListNode p=3) {
					// 只剩一个节点，返回
                    return 3
                }
            }
            return 2
        }
        return 1
    }
}

代码

public ListNode deleteDuplicates(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    if(p.val == p.next.val) {
        return deleteDuplicates(p.next);
    } else {
        p.next = deleteDuplicates(p.next);
        return p;
    }
}

5.有序链表去重-力扣 82 题

例如

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

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

注意：重复元素一个不留

1.解法一

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

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

deleteDuplicates(ListNode p = 1) {
    // 找下个不重复的
	deleteDuplicates(ListNode p = 1) {
        deleteDuplicates(ListNode p = 1) {
			          deleteDuplicates(ListNode p = 2) {
                      2.next=deleteDuplicates(ListNode p = 3) {
                        // 只剩一个节点，返回
                        return 3
                }
                return 2
			}
        }
    }
}

代码

public ListNode deleteDuplicates(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    if (p.val == p.next.val) {
        ListNode x = p.next.next;
        while (x != null && x.val == p.val) {
            x = x.next;
        }
        return deleteDuplicates(x);
    } else {
        p.next = deleteDuplicates(p.next);
        return p;
    }
}

2.解法二

p1 是待删除的上一个节点，每次循环对比 p2、p3 的值

• 如果 p2 与 p3 的值重复，那么 p3 继续后移，直到找到与 p2 不重复的节点，p1 指向 p3 完成删除
• 如果 p2 与 p3 的值不重复，p1，p2，p3 向后平移一位，继续上面的操作
• p2 或 p3 为 null 退出循环
  • p2 为 null 的情况，比如链表为 1 1 1 null

p1 p2 p3
s, 1, 1, 1, 2, 3, null

p1 p2    p3
s, 1, 1, 1, 2, 3, null

p1 p2       p3
s, 1, 1, 1, 2, 3, null

p1 p3
s, 2, 3, null

p1 p2 p3
s, 2, 3, null

   p1 p2 p3
s, 2, 3, null

代码

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2;
    ListNode p3;
    while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
        if (p2.val == p3.val) {
            while ((p3 = p3.next) != null
                   && p3.val == p2.val) {
            }
            p1.next = p3;
        } else {
            p1 = p1.next;
        }
    }
    return s.next;
}

6.合并有序链表-力扣 21 题

例

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

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

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

1.解法一

• 谁小，把谁链给 p，p 和小的都向后平移一位
• 当 p1、p2 有一个为 null，退出循环，把不为 null 的链给 p

p1
1	3	8	9	null

p2
2	4	null

p
s	null

代码

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
    ListNode s = new ListNode(-1, null);
    ListNode p = s;
    while (p1 != null && p2 != null) {
        if (p1.val < p2.val) {
            p.next = p1;
            p1 = p1.next;
        } else {
            p.next = p2;
            p2 = p2.next;
        }
        p = p.next;
    }
    if (p1 != null) {
        p.next = p1;
    }
    if (p2 != null) {
        p.next = p2;
    }
    return s.next;
}

• 可以自行验证例中后两种情况

2.解法二

递归函数应该返回

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

mergeTwoLists(p1=[1,3,8,9], p2=[2,4]) {
    1.next=mergeTwoLists(p1=[3,8,9], p2=[2,4]) {
        2.next=mergeTwoLists(p1=[3,8,9], p2=[4]) {
            3.next=mergeTwoLists(p1=[8,9], p2=[4]) {
                4.next=mergeTwoLists(p1=[8,9], p2=null) {
                    return [8,9]
                }
                return 4
            }
            return 3
        }
        return 2
    }
	return 1
}

代码

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
    if (p2 == null) {
        return p1;
    }
    if (p1 == null) {
        return p2;
    }
    if (p1.val < p2.val) {
        p1.next = mergeTwoLists(p1.next, p2);
        return p1;
    } else {
        p2.next = mergeTwoLists(p1, p2.next);
        return p2;
    }
}

7.合并多个有序链表-力扣 23 题

例

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

递归

public ListNode mergeKLists(ListNode[] lists) {
    if (lists.length == 0) {
        return null;
    }
    return merge(lists, 0, lists.length - 1);
}

public ListNode split(ListNode[] lists, int i, int j) {
    System.out.println(i + " " + j);
    if (j == i) {
        return lists[i];
    }
    int m = (i + j) >>> 1;
    return mergeTwoLists(
        split(lists, i, m),
        split(lists, m + 1, j)
    );
}

还可以用优先级队列求解，这个放在后面讲

8.查找链表中间节点-力扣 876 题

例如

输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])

输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])

• 偶数节点时，中间点是靠右的那个

解法：快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到链表结尾时，慢指针恰好走到链表的一半

public ListNode middleNode(ListNode head) {
    ListNode p1 = head;	// 慢指针，中间点
    ListNode p2 = head;	// 快指针
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
        p2 = p2.next;
    }
    return p1;
}

9.回文链表-力扣 234 题

所谓回文指正着读、反着读，结果一样，例如

[1,2,2,1]
[1,2,3,2,1]

它们都是回文链表，不是回文的例子

[1,2,3,1]  --反过来-->  [1,3,2,1]

解法

/*
    步骤1. 找中间点
    步骤2. 中间点后半个链表反转
    步骤3. 反转后链表与原链表逐一比较
*/
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;
}

private ListNode reverse(ListNode o1) {
    ListNode n1 = null;
    while (o1 != null) {
        ListNode o2 = o1.next;
        o1.next = n1;
        n1 = o1;
        o1 = o2;
    }
    return n1;
}

private ListNode middle(ListNode head) {
    ListNode p1 = head; // 慢
    ListNode p2 = head; // 快
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;
    }
    return p1;
}

优化后解法

public boolean isPalindrome(ListNode h1) {
    if (h1 == null || h1.next == null) {
        return true;
    }
    ListNode p1 = h1; 	// 慢指针，中间点
    ListNode p2 = h1; 	// 快指针
    ListNode n1 = null;	// 新头
    ListNode o1 = h1;	// 旧头
    // 快慢指针找中间点
    while (p2 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next.next;

        // 反转前半部分
        o1.next = n1;
        n1 = o1;
        o1 = p1;
    }
    if (p2 != null) { // 节点数为奇数
        p1 = p1.next;
    }
    // 同步比较新头和后半部分
    while (n1 != null) {
        if (n1.val != p1.val) {
            return false;
        }
        p1 = p1.next;
        n1 = n1.next;
    }
    return true;
}

10.环形链表-力扣 141 题

本题以及下题，实际是 Floyd's Tortoise and Hare Algorithm （Floyd 龟兔赛跑算法）

除了 Floyd 判环算法外，还有其它的判环算法，详见 https://en.wikipedia.org/wiki/Cycle_detection

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

阶段 1

• 龟一次走一步，兔子一次走两步
• 当兔子能走到终点时，不存在环
• 当兔子能追上龟时，可以判断存在环

阶段 2

• 从它们第一次相遇开始，龟回到起点，兔子保持原位不变
• 龟和兔子一次都走一步
• 当再次相遇时，地点就是环的入口

为什么呢？

• 设起点到入口走 a 步（本例是 7），绕环一圈长度为 b（本例是 5），
• 那么从起点开始，走 a + 绕环 n 圈，都能找到环入口
• 第一次相遇时
  • 兔走了 a + 绕环 n 圈（本例 2 圈） + k，k 是它们相遇距环入口位置（本例 3，不重要）
  • 龟走了 a + 绕环 n 圈（本例 0 圈） + k，当然它绕的圈数比兔少
  • 兔走的距离是龟的两倍，所以龟走的 = 兔走的 - 龟走的 = 绕环 n 圈
• 而前面分析过，如果走 a + 绕环 n 圈，都能找到环入口，因此从相遇点开始，再走 a 步，就是环入口

阶段 1 参考代码（判断是否有环）

public boolean hasCycle(ListNode head) {
    ListNode h = head; // 兔
    ListNode t = head; // 龟
    while (h != null && h.next != null) {
        t = t.next;
        h = h.next.next;
        if(h == t){
            return true;
        }
    }
    return false;
}

11.环形链表-力扣 142 题

阶段 2 参考代码（找到环入口）

public ListNode detectCycle(ListNode head) {
    ListNode t = head; // 龟
    ListNode h = head; // 兔
    while (h != null && h.next != null) {
        t = t.next;
        h = h.next.next;
        if (h == t) {
            t = head;
            while (true) {
                if (h == t) {
                    return h;
                }
                h = h.next;
                t = t.next;
            }
        }
    }
    return null;
}

• 还有一道扩展题目，也可以用判环算法思想来解：就是 287 题，寻找重复数

12.删除节点-力扣 237 题

这道题目比较简单，留给大家自己练习

例如

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]

注意：被删除的节点不是末尾节点

参考答案

public class Ex1Leetcode237 {
    /**
     *
     * @param node 待删除节点, 题目已说明肯定不是最后一个节点
     */
    public void deleteNode(ListNode node) {
        node.val = node.next.val;		// 下一个节点值赋值给待"删除"节点
        node.next = node.next.next;		// 把下一个节点删除
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        new E0xLeetcode237().deleteNode(o3);
        System.out.println(o1);
    }
}

输出

[1,2,3,4,5]
[1,2,4,5]

13.共尾链表-力扣 160 题

原题叫做相交链表，个人觉得用共尾链表更形象些，此题更像是一道脑筋急转弯，留给大家练习

例如，下图的两个链表 [1, 2, 4, 5] 与 [3, 4, 5] 它们中 [4, 5] 是相同的，此时应返回节点 4

非共尾的情况，如下图所示，此时返回 null

思路，称两个链表为 a=[1, 2, 4, 5]，b=[3, 4, 5]，图中用 N 代表 null

1. 遍历 a，遇到 null 时改道遍历 b
2. 与此同时，遍历 b，遇到 null 时改道遍历 a
3. 在此过程中，如果遇到相同的节点，即为找寻目标，返回即可，如下图中的第二次出现的 4
4. 相同节点应该比较其引用值，图中数字只是为了便于区分

1	2	4	5	N	3	4	5	N
3	4	5	N	1	2	4	5	N

如果两个链表长度相同，则可以更早找到目标，例如 a=[1, 4, 5]，b=[3, 4, 5]，第一次出现 4 时，即可返回

1	4	5	N	3	4	5	N
3	4	5	N	1	4	5	N

如果是非共尾的情况，如 a=[1, 2, 4]，b=[3, 5]，可以看到，唯一相等的情况，是遍历到最后那个 N 此时退出循环

1	2	4	N	3	5	N
3	5	N	1	2	4	N

代码

public ListNode getIntersectionNode(ListNode a, ListNode b) {
    ListNode p1 = a;
    ListNode p2 = b;
    while (true) {
        if (p1 == p2) {
            return p1;
        }
        if (p1 == null) {
            p1 = b;
        } else {
            p1 = p1.next;
        }
        if (p2 == null) {
            p2 = a;
        } else {
            p2 = p2.next;
        }
    }
}

14.两数相加-力扣 2 题

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

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

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

示例 1：

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

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

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

题解:

具体实现步骤如下：

1. 首先，我们需要创建一个新的链表，用来存储两个链表相加的结果。同时，我们需要定义一个指针，用来遍历链表。
2. 接着，我们可以从两个链表的头节点开始，依次遍历它们的每一个节点，将它们对应位置的数字相加，并记录进位。
3. 如果其中一个链表已经遍历结束，我们就可以直接将另一个链表剩余的部分接到结果链表的后面（注意，这里还需要考虑进位）。
4. 最后，如果遍历完成后还有进位，我们就需要在结果链表的末尾添加一个新节点，存储进位。

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        """
        链表遍历
        :param l1:
        :param l2:
        :return:
        """
        res = ListNode(0)
        cur = res
        carry = 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = x + y + carry
            carry = s // 10
            cur.next = ListNode(s % 10)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry:
            cur.next = ListNode(carry)
        return res.next

时间复杂度：O(max(m, n))，其中 m 和 n 分别是 l1 和 l2 的长度。

空间复杂度：O(max(m, n))，我们需要使用一个链表来存储结果。

15.两数相加 II-力扣 445 题

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

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

示例 1：

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

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

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

题解:

解题思路：

1. 先把两个链表逆序，使得最低位在链表头部，这样就可以从头部开始相加了。
2. 定义一个 carry 变量，表示进位，初始值为 0。
3. 定义一个新的链表 dummyHead，表示相加的结果。
4. 从链表 1 和链表 2 的头部开始遍历，对于每一位进行相加，同时加上进位 carry。
5. 如果当前的和大于等于 10，就需要进位，将 carry 变为 1，同时将和减去 10。
6. 将当前的和插入到新的链表 dummyHead 的末尾。
7. 遍历完链表 1 和链表 2 后，如果进位 carry 为 1，还需要将 carry 插入到 dummyHead 的末尾。
8. 最后将 dummyHead 逆序，得到正常的结果链表。

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


# 翻转链表
def reverseList(head: ListNode) -> ListNode:
    pre = None
    curr = head
    while curr:
        next = curr.next
        curr.next = pre
        pre = curr
        curr = next
    return pre


class Solution:
    def addTwoNumbers(self, l11: Optional[ListNode], l22: Optional[ListNode]) -> Optional[ListNode]:
        l1 = reverseList(l11)
        l2 = reverseList(l22)
        res = ListNode(0)
        cur = res
        carry = 0
        while l1 or l2:
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            s = x + y + carry
            carry = s // 10
            cur.next = ListNode(s % 10)
            cur = cur.next
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next
        if carry:
            cur.next = ListNode(carry)
        return reverseList(res.next)

16.删除链表的中间节点-力扣 2095 题

给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。 长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。 对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

输入：head = [1,3,4,7,1,2,6]
输出：[1,3,4,1,2,6]
解释：
上图表示给出的链表。节点的下标分别标注在每个节点的下方。
由于 n = 7 ，值为 7 的节点 3 是中间节点，用红色标注。
返回结果为移除节点后的新链表。

public ListNode deleteMiddle(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    ListNode fast = head;
    ListNode slow = head;
    ListNode pre = null;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = pre.next.next;
    return head;
}

17.排序链表-力扣 148 题

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

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

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode slow = getMidListNode(head);
    //分割链表
    ListNode mid = slow.next;
    slow.next = null;
    ListNode left = sortList(head);
    ListNode right = sortList(mid);
    //合并链表
    return merge(left, right);
}


/**
 * 获取中间节点
 *
 * @param head
 * @return
 */
private ListNode getMidListNode(ListNode head) {
    //找中间节点
    ListNode fast = head.next;
    ListNode slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
}

public ListNode merge(ListNode node1, ListNode node2) {
    ListNode s = new ListNode(0, null);
    ListNode curr = s;
    while (node1 != null && node2 != null) {
        if (node1.val < node2.val) {
            curr.next = node1;
            node1 = node1.next;
        } else {
            curr.next = node2;
            node2 = node2.next;
        }
        curr = curr.next;
    }
    curr.next = node1 == null ? node2 : node1;
    return s.next;
}

八.反转链表

1.反转链表-力扣 206 题

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

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

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

输入：[]
输出：[]

1.解法一-迭代-新链表

构造一个新链表，从旧链表依次拿到每个节点，创建新节点添加至新链表头部，完成后新链表即是倒序的

评价：简单直白，就是得新创建节点对象

// 创建新节点
public ListNode reverseList(ListNode o1) {
    //创建新的链表空节点
    ListNode n1 = null;
    //设置临时节点,把o1指向p
    ListNode p = o1;
    while (p != null) {
        //创建节点,新节点的下一个节点是新链表,并重置新链表的头部
        n1 = new ListNode(p.val, n1);
        //移动旧链表的位置
        p = p.next;
    }
    //因为重置了n1,直接返回n1
    return n1;
}

2.解法二-迭代-存取

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

评价：更加面向对象，如果实际写代码而非刷题，更多会这么做

// 设计一个List
public ListNode reverseList(ListNode head) {
    //旧链表
    List o1 = new List(head);
    //新链表
    List n1 = new List(null);
    while (true) {
        //不断取旧链表的第一个元素
        final ListNode listNode = o1.removeFirst();
        //如果旧链表为空，则跳出循环
        if (listNode == null) {
            break;
        }
        //将旧链表的第一个元素添加到新链表的头部
        n1.addFirst(listNode);
    }
    return n1.head;
}

static class List {
    ListNode head;

    public List(ListNode head) {
        this.head = head;
    }


    /**
     * 添加到头节点
     *
     * @param first
     */
    public void addFirst(ListNode first) {
        //头节点的下一个节点是head
        first.next = head;
        //重置head
        head = first;
    }

    /**
     * 删除头节点
     *
     * @return
     */
    public ListNode removeFirst() {
        //此时的head是旧链表的head,需要截断头节点,并返回完整的节点
        ListNode first = head;
        if (first != null) {
            head = first.next;
        }
        return first;
    }
}

3.解法三-迭代

从链表每次拿到第二个节点，将其从链表断开，插入头部，直至它为 null 结束

1. 设置指针 o1(旧头)、n1(新头)、o2(旧老二)，分别指向第一，第一，第二节点

$\frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

2. 将 o2 节点从链表断开，即 o1 节点指向第三节点

$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ ，$\frac{o2}{2}$

3. o2 节点链入链表头部，即

$\frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

4. n1 指向 o2

$\frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

5. o2 指向 o1 的下一个节点，即

$\frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null$

6. 重复以上 $2\sim5$ 步，直到 o2 指向 null

7. 还应当考虑边界条件，即链表中不满两个元素时，无需走以上逻辑

/**
 * 不断把 o2 头插入 n1
 *
 * @param o1
 * @return
 */
public ListNode reverseList(ListNode o1) {
    // 1. 空链表  2. 一个元素
    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
        n1 = o2;
        //重置o2
        o2 = o1.next;
    }
    return n1;
}

4.解法四-迭代-常用

要点：把链表分成两部分，思路就是不断从链表 2 的头，往链表 1 的头搬移

1. n1 指向 null，代表新链表一开始没有元素，o1 指向原链表的首节点

$\frac{n1}{null}$，$\frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

2. 开始循环，o2 指向原链表次节点

$\frac{n1}{null}$，$\frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

3. 搬移

$\frac{o1}{1} \rightarrow \frac{n1}{null}$ ， $\frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

4. 指针复位

$\frac{n1}{1} \rightarrow null$ ， $\frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$

5. 重复 $2\sim4$ 步
6. 当 o1 = null 时退出循环

//不断把 o1 头插到 n1
public ListNode reverseList(ListNode o1) {
    if (o1 == null || o1.next == null) {
        return o1;
    }
    //创建空链表
    ListNode n1 = null;
    while (o1 != null) {
        ListNode o2 = o1.next;
        //取出节点后指向新节点
        o1.next = n1;
        //重置n1
        n1 = o1;
        //重置o1
        o1 = o2;
    }
    return n1;
}

5.解法五-递归-常用

递归，在递归时让 $5 \rightarrow 4$，$4 \rightarrow 3$ ...

首先，写一个递归方法，返回值用来拿到最后一个节点

• 注意 1：递归终止条件是 curr.next == null，目的是到最后一个节点就结束递归，与之前递归遍历不一样
• 注意 2：需要考虑空链表即 p == null 的情况

下面为伪码调用过程，假设节点分别是 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$，先忽略返回值

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    	reverseList(ListNode p = 3) {
    		reverseList(ListNode p = 4) {
    			reverseList(ListNode p = 5) {
    				if (p == null || p.next == null) {
                        return p; // 返回5
                    }
				}
                // 此时p是4, p.next是5
			}
            // 此时p是3, p.next是4
		}
        // 此时p是2, p.next是3
	}
    // 此时p是1, p.next是2
}

接下来，从 p = 4 开始，要让 $5 \rightarrow 4$，$4 \rightarrow 3$ ...

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    	reverseList(ListNode p = 3) {
    		reverseList(ListNode p = 4) {
    			reverseList(ListNode p = 5) {
    				if (p == null || p.next == null) {
                        return p; // 返回5
                    }
				}
                // 此时p是4, p.next是5, 要让5指向4,代码写成 p.next.next=p
                // 还要注意4要指向 null, 否则就死链了
			}
            // 此时p是3, p.next是4
		}
        // 此时p是2, p.next是3
	}
    // 此时p是1, p.next是2
}

最终解法

//递归
public ListNode reverseList(ListNode p) {
    if (p == null || p.next == null) {
        return p; // 最后节点
    }
    ListNode last = reverseList(p.next);
    //这里最后一个节点是倒数第二个节点
    p.next.next = p;
    //防止死循环,环形链表
    p.next = null;
    return last;
}

6.解法六-递归-常用

public ListNode reverseList(ListNode head) {
    return reverse(head, null);
}

public ListNode reverse(ListNode node, ListNode pre) {
    //到了链表结尾
    if (node == null) {
        //这就是要返回的新头节点
        return pre;
    }
    ListNode res = reverse(node.next, node);
    //后序遍历
    node.next = pre;
    return res;
}

2.翻转链表前 n 个节点

和反转整个链表相比，反转前 n 个节点，程序结束在第 n 个节点处，还需要把第 n+1 个后继节点 succ 记录下来，因为他是反转后的前 n 个节点跟后边剩余节点的连接点。

public class E14Leetcode {
    ListNode succeedNode = null;

    /**
     * 翻转指定区间的链表
     *
     * @param head
     * @return
     */
    public ListNode reverseBetween(ListNode head, int n) {
      	//递归结束的地方
        if (n == 1) {
            //记录后继节点,第一次记录的后继是3,因为2-->3
            succeedNode = head.next;
            return head;//返回节点2
        }
        final ListNode last = reverseBetween(head.next, n - 1);
        //这里的的head是1,1节点的下一个节点的下一个节点
        head.next.next = head;//相当于翻转2 --> 1
        head.next = succeedNode;//head是1,把1和3连起来  1-->3
        return last;
    }

    public static void main(String[] args) {
        ListNode node = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(new E14Leetcode().reverseBetween(node, 2).toString());
    }
}

3.反转链表 II-力扣 92 题

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

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

public class E03Leetcode92 {
    private ListNode succeedNode;

    /**
     * 翻转指定区间的链表
     *
     * @param head
     * @param left
     * @param right
     * @return
     */
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //开始反转的位置,left==1 说明就是反转 前right 个节点
        if (left == 1) {
            //2->3->4>5
            //反转后4->3->2->5
            //调用反转前N个节点的程序
            return reverse(head, right);//反转前3个
        }
        //递归反转前n个节点
        //1-->链上前面的 4->3->2->5
      	//left 不为1，那就向后滑动，然后就会遇到
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    /**
     * 反转前n个节点
     *
     * @param head
     * @param n
     * @return
     */
    private ListNode reverse(ListNode head, int n) {
        if (n == 1) {
            //记录后继节点,第一次记录的后继是3,因为2-->3
            succeedNode = head.next;
            return head;//返回节点2
        }
        final ListNode last = reverse(head.next, n - 1);
        //这里的的head是1,1节点的下一个节点的下一个节点
        head.next.next = head;//相当于翻转2 --> 1
        head.next = succeedNode;//head是1,把1和3连起来  1-->3
        return last;
    }

    public static void main(String[] args) {
        ListNode node = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(new E03Leetcode92().reverseBetween(node, 2, 4).toString());
    }
}

4.K 个一组翻转链表-力扣 25 题

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

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

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

题解:

public class E04Leetcode25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return null;
        }
      	//a,b区间包含k个待翻转的元素
        ListNode a = head;
        ListNode b = head;
        for (int i = 0; i < k; i++) {
          	//不够k个时
            if (b == null) {
                return head;
            }
            b = b.next;
        }
      	//反转前k个后的新头节点
        ListNode n1 = reverse(a, b);
      	//递归：反转后续链表并拼接起来
        a.next = reverseKGroup(b, k);
        return n1;
    }

  	//辅助函数,翻转ab之间的节点,并返回新的头节点
    private ListNode reverse(ListNode a, ListNode b) {
        ListNode pre = null;
        ListNode curr = a;
        while (curr != b) {
            final ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    public static void main(String[] args) {
        ListNode node = ListNode.of(1, 2, 3, 4, 5);
        System.out.println(new E04Leetcode25().reverseKGroup(node, 3).toString());
    }
}