未命名

发表于 2025-03-13 更新于 2024-11-13 阅读次数： Waline：本文字数： 22k 阅读时长 ≈ 37 分钟

毛毛张分享的本篇博客是对《代码随想录》中的链表一章的LeetCode题目解法的总结，一共包含了八道题目，毛毛张全部使用Java代码进行编写，并在第3题中给出了毛毛张递归的解法，这个题目如果清楚递归的逻辑，用递归求解是比较方便的

[toc]

1.链表基础理论

在刷下面的LeetCode题目之前，让我们先来回顾一下链表的相关基础知识！

1.1 什么是链表？

链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域(存放指向下一个节点的指针)，最后一个节点的指针域指向null（空指针的意思），链表的入口节点称为链表的头节点也就是head，如下图所示

1.2 链表的类型

单链表：上面说的就是单链表，单链表中的指针域只能指向节点的下一个节点
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点，因此双链表既可以向前查询也可以向后查询，如下图所示：

循环链表： 即链表首尾相连，循环链表可以用来解决约瑟夫问题，如下图所示：

1.3 链表结点定义

在平时刷LeetCode的时候，链表的结点都默认定义好了，但是在面试的是时候可能不会给出，所以大家一定要熟悉链表结点的定义

public class ListNode {
    // 结点的值
    int val;

    // 下一个结点
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }

    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }

    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

1.4 链表的操作

对于不同类型的数据结构无外乎四种操作：增、删、改、查，对于链表来说，后面两种操作比较简单，复杂的是删除结点和增加结点

1.4.1 删除结点

下图展示了要删除一个结点的操作的图解，假设要删除的结点是D结点，如果要删除D结点就只需要找到要删除的结点的前一个结点C，然后将C结点的next指针指向E结点就可以了

删除操作最关键的是找到要删除的结点的前面一个结点，上图中cur指向的是要删除的结点、pre指向的是要删除的结点的前面一个结点
1
2
//删除操作
pre.next = cur.next;

1.4.2 增加结点

下图展示的是要增加的一个结点的操作的图解。

假设要在索引为3的位置(D结点)插入结点F，上图中cur指向的是要插入位置的结点、pre指向的是要插入的位置的前一个结点
1
2
3
4
5
//创建要插入的结点
ListNode F = new ListNode(val);
cur = pre.next;
pre.next = F;
F.next = cur;

1.5 小结

链表的长度是不固定的，并且可以动态增删，适合数量不固定，频繁增删，较少查询的场景
上面知识对链表的相关知识点进行了一个简单的回顾，更多的可以参见毛毛张的这篇博客：

2.203. 移除链表元素

LeetCode标签：简单

2.1 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50

2.2 题解

2.2.1 迭代

写法1：直接使用原来的链表来进行移除结点操作

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //判断特殊情况
        //if(head == null) return null;

        //判断如果删除的是第一个结点
        while(head != null && head.val ==val){
            head = head.next;
        }

        //定义结点用来记录要删除的结点的前一个结点
        ListNode pre = head;
        while(pre != null){
            if(pre.next != null && val == pre.next.val){
                pre.next = pre.next.next;
            }else{
                pre = pre.next;
            }
        }
        //返回结果
        return head;
    }
}

图解： 以链表 1->2->6->3->4->5->6, val = 6 为例

首先，pre 指向 head
当 pre 指向的节点的下一个节点的值不等于 val 时，右移 pre 进行遍历
等于时，将 pre 指向其下一个节点的下一个节点，相当于删除了 pre 之前指向节点的下一个节点
继续遍历，操作步骤跟前面两步一样

处理后的结果：

看到上面的代码发现有两种情况，原因就是头节点也存储了元素，如果要删除的第一个结点的时候，无法知道该头节点的前一个结点，无法进行统一的删除结点操作，于是我们可以虚设一个头节点，这样就方便执行统一的删除操作

写法2：设置一个虚拟头结点在进行移除节点操作

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //判断特殊情况
        if (head == null) return head;

        //创建一个新的头节点
        ListNode newHead = new ListNode(0,head);

        //创建指针，用来指示要删除的结点前一个结点
        ListNode pre = newHead;
        //开始迭代，寻找要删除的结点
        while(pre != null){
            if(pre.next != null && pre.next.val == val){
                pre.next = pre.next.next;
            }else{
                pre = pre.next;
            }
        }
        //返回结果
        return newHead.next;
    }
}

代码说明：

设置一个虚拟头节点之后，要删除题设链表的第一个结点的操作和后面一个结点的操作就是相同的，整个代码逻辑比较清晰，毛毛张就不在这里过多阐述了

2.2.2 递归

分析：

链表具有天然的递归性，我们要删除整个链表中符合条件的结点，可以递归到更短的链表，删除短的链表中符合条件的结点

上面的迭代法是从前往后进行删除，因此在删除前需要知道要删除的结点的前一个结点，而递归法的逻辑则是从后往前处理
递归法的代码比较简洁，大家可以先看代码，然后再看图解，大家一定要理解这个逻辑，我们可以通过这个思路来求解第三题

代码：

class Solution {
    //递归法 三步走
    //1.确定形参和返回值
    public ListNode removeElements(ListNode head, int val) {
        //2.确定终止条件
        if(head == null) return null;

        //3.确定单层递归逻辑
        //递归到最后一个结点才进行删除操作，从后往前
        head.next = removeElements(head.next,val);
        return head.val == val ? head.next : head;
    }
}

图解：

2_3

看完递归求解上面这个题目，大家可以使用递归法来求解下面这道题目

3.19. 删除链表的倒数第 N 个结点

LeetCode标签：中等

3.1 题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

3.2 题解

3.2.1 迭代

方法1：暴力解法

首先计算链表的长度$Length$
删除倒数第$N$个结点，就是删除正着数的第$Length-N+1$个结点
删除第$Length-N+1$个结点，需要找到要删除结点的前一个结点，就是第$Length-N$个节点

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //获取链表的长度
        int length = getLength(head);

        //判断要删除的节点位置
        int index = length - n;

        //判断是不是要删除第一个节点
        if(index == 0) return head.next;

        //如果不是迭代到要删除的节点的前一个结点
        ListNode pre = null;//要删除的结点的前一个结点
        ListNode cur = head;//要删除的结点
        for(int i=0;i<index;i++){
            pre = cur;
            cur = cur.next;
        }
        //执行删除操作
        pre.next = cur.next;
        
        return head;
    }
    public int getLength(ListNode head){
        int length = 0;
        while(head != null){
            length++;
            head = head.next;
        }
        return length;
    }
}

方法2：借助栈

思路：

我们也可以在遍历链表的同时将所有节点依次入栈。
根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //虚设一个头节点  
        ListNode newHead = new ListNode(0,head);
        //创建栈用于存储链表结点
        Stack<ListNode> stack = new Stack<>();
        //开始迭代，所有结点入栈
        ListNode cur = newHead;
        while(cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        //从栈顶开始弹出元素，一直弹到要删除的位置
        for(int i=0;i<n;i++){
            stack.pop();
        }
        //再弹出的元素就是要删除的结点的前一个元素
        ListNode pre = stack.pop();
        //删除操作
        pre.next = pre.next.next;
        //返回结果
        return newHead.next;
    }
}

图解：

方法3：双指针法

思路：

由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了 n−1 个节点，即 first 比 second 超前了 n 个节点。

在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

根据方法一和方法二，如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点，其余的操作步骤不变。这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

图解：

代码：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //虚设头节点
        ListNode newHead = new ListNode(0,head);

        //创建两个指针，两个指针之间相差n结点
        ListNode first = newHead;
        ListNode second = newHead;
        for(int i=0;i<=n;i++){
            first = first.next;
        }

        //开始迭代
        while(first != null){
            first = first.next;
            second = second.next;
        }

        //开始移除
        second.next = second.next.next;

        return newHead.next;
    }
}

3.2.2 递归

思路：

上面介绍过一种方法，利用栈来存储元素，迭代到链表的尾部，再从栈顶弹出n个结点就是倒数第n个结点
然而递归的本质也是栈，所以我们也可以尝试使用递归的方式，递归到链表的尾部，再从后往前处理
代码如下，代码本身比较简洁，如果对代码的逻辑不理解的可以结合着下面的动态图来理解

代码：

class Solution {
    int count = 0;
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //判断特殊情况
        if(head == null) return null;

        //确定单层递归逻辑
        //递归到最后一个元素
        head.next = removeNthFromEnd(head.next,n);
        //开始回溯
        count++;
        if(count == n){
            return head.next;
        }else{
            return head;
        }
    }
}

图解：

3_2

4.707. 设计链表

4.1 题目描述

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

MyLinkedList() 初始化 MyLinkedList 对象。
int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

0 <= index, val <= 1000
请不要使用内置的 LinkedList 库。
调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

4.2 题解

这个题目是对单链表和双链表的基本操作的考察

4.2.1 单链表

写法1

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {
    //定义变量存储链表元素的个数
    int size;
    //定义虚拟头节点
    ListNode head;

    public MyLinkedList() {
        //初始化链表实现类
        this.size = 0;
        this.head = new ListNode(0);
    }
    
    public int get(int index) {
        //判断特殊情况
        if(index < 0 || index >= this.size) return -1;
        //定义迭代的当前节点
        ListNode cur = head;
        //开始迭代
        for(int i=0;i<=index;i++){
            cur = cur.next;
        }
        //返回结果
        return cur.val;
    }
    //头插法
    public void addAtHead(int val) {
        //实例化要插入的节点
        ListNode node = new ListNode(val);
        //开始执行插入操作
        ListNode temp = head.next;
        node.next = temp;
        head.next = node;
        //更新链表存储的元素
        this.size++;
    }
    //尾插法
    public void addAtTail(int val) {
        //实例化要插入的节点
        ListNode node = new ListNode(val);
        //定义迭代的当前节点
        ListNode cur = head;
        //开始迭代
        for(int i=0;i<this.size;i++){
            cur = cur.next;
        }
        //直接把新节点插入作为最后一个节点的next
        cur.next = node;
        //更新链表存储的元素
        this.size++;
    }
    
    public void addAtIndex(int index, int val) {
        //判断特殊情况
        if(index < 0 || index > this.size){
            return;
        }else if(index == this.size){
            //要插入的位置正好是在链表的尾部
            addAtTail(val);
            return;
        }
        //定义迭代的当前节点
        ListNode cur = head;
        //开始迭代
        for(int i=0;i<index;i++){
            cur = cur.next;
        }
        //定义要插入的节点
        ListNode node = new ListNode(val);
        //开始执行插入操作
        ListNode temp = cur.next;
        node.next = temp;
        cur.next = node;
        //更新链表存储的元素
        this.size++;
    }
    
    public void deleteAtIndex(int index) {
        //判断删除的下标是否有效
        if(index < 0 || index >= this.size) return;

        //更新链表存储的元素
        size--;
        //如果是删除第一个元素
        if(index == 0){
            head = head.next;
            return;
        }
        
        //定义迭代的当前节点
        ListNode pre = head;
        //开始迭代
        //迭代到当前要删除的下标的前面一个节点
        for(int i=0;i<index;i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

写法1优化

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {
    //定义变量存储链表元素的个数
    int size;
    //定义虚拟头节点
    ListNode head;

    public MyLinkedList() {
        //初始化链表实现类
        this.size = 0;
        //初始化虚拟头节点
        this.head = new ListNode(0);
    }
    
    public int get(int index) {
        //判断特殊情况:不正确的index
        if(index < 0 || index >= this.size) return -1;
        //定义迭代的当前节点
        ListNode cur = head;
        //开始迭代
        for(int i=0;i<=index;i++){
            cur = cur.next;
        }
        //返回结果
        return cur.val;
    }
    //头插法
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //尾插法
    public void addAtTail(int val) {
        addAtIndex(this.size,val);
    }
    
    public void addAtIndex(int index, int val) {
        //如果index大于链表的长度，则返回空
        if(index > size) return;
        if(index < 0) index = 0;
        //在第index个节点之前插入一个新节点，如果index=0，哪个插入的新节点的为链表的新头节点
        //如果index等于链表的长度，则说明新插入的节点要插入链表的尾部
        //更新链表存储的元素
        this.size++;
        //找到要插入的节点的前驱
        ListNode pre = head;
        for(int i=0;i<index;i++){
            pre = pre.next;
        }
        //创建要插入的节点
        ListNode node = new ListNode(val);
        //插入操作
        node.next = pre.next;
        pre.next = node;
    }
    
    public void deleteAtIndex(int index) {
        //判断删除的下标是否有效
        if(index < 0 || index >= this.size) return;

        //更新链表存储的元素
        size--;
        
        //如果是删除第一个元素
        if(index == 0){
            head = head.next;
            return;
        }

        //定义迭代的当前节点
        ListNode pre = head;
        //开始迭代
        //迭代到当前要删除的下标的前面一个节点
        for(int i=0;i<index;i++){
            pre = pre.next;
        }
        pre.next = pre.next.next;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

4.2.2 双链表

//双向链表
class ListNode {
    int val;
    ListNode next;
    ListNode pre;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {
    //定义变量存储链表元素的个数
    int size;
    //定义虚拟头节点
    ListNode head;
    //定义虚拟尾节点
    ListNode tail;

    public MyLinkedList() {
        //初始化链表实现类
        this.size = 0;
        //初始化虚拟头节点
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int index) {
        //判断特殊情况:不正确的index
        if(index < 0 || index >= this.size) return -1;
        //定义迭代的当前节点
        ListNode cur;
        //判断从前迭代还是从后迭代
        if (index + 1 <= size - index) {
            cur = this.head;
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
        } else {
            cur = this.tail;
            for (int i = 0; i < size - index; i++) {
                cur = cur.pre;
            }
        }
        //返回结果
        return cur.val;
    }
    //头插法
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    //尾插法
    public void addAtTail(int val) {
        addAtIndex(this.size,val);
    }
    
    public void addAtIndex(int index, int val) {
        //如果index大于链表的长度，则返回空
        if(index > size) return;
        index = Math.max(0,index);
        //在第index个节点之前插入一个新节点，如果index=0，哪个插入的新节点的为链表的新头节点
        //如果index等于链表的长度，则说明新插入的节点要插入链表的尾部
        
        //定义要插入的节点的前驱和后继
        ListNode pre,post;
        if(index < size - index){
            pre = this.head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            post = pre.next;
        }else{
            post = this.tail;
            for(int i = 0; i < size-index; i++){
                post = post.pre;
            }
            pre = post.pre;
        }
        //创建要插入的节点
        ListNode node = new ListNode(val);
        //插入操作
        node.pre = pre;
        node.next = post;
        pre.next = node;
        post.pre = node;
        //更新链表存储的元素
        this.size++;
    }
    
    public void deleteAtIndex(int index) {
        //判断删除的下标是否有效
        if(index < 0 || index >= this.size) return;

        //定义要插入的节点的前驱和后继
        ListNode pre,post;
        if(index < size - index){
            pre = this.head;
            for(int i = 0; i < index; i++){
                pre = pre.next;
            }
            post = pre.next.next;
        }else{
            post = this.tail;
            for(int i = 0; i < size - index -1; i++){
                post = post.pre;
            }
            pre = post.pre.pre;
        }

        //执行删除操作
        pre.next = post;
        post.pre = pre;
        //更新链表存储的元素
        this.size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

5.206. 反转链表

LeetCode标签：简单

5.1 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

5.2 题解

这个题目毛毛张还是从迭代和递归的角度分享解法

5.2.1 迭代

迭代法的思路就是在迭代原始链表的元素的过程中，用头插法创建一个新的链表就可以实现反转的目的

写法1

class Solution {
    public ListNode reverseList(ListNode head) {
        //创建反转链表的头
        ListNode newHead = null;
        //获取当前插入结点
        ListNode cur = head;
        while(cur != null){
            //获取当前结点的值
            int val = cur.val;
            //新建插入结点
            ListNode node = new ListNode(val);
            if(newHead == null){
                newHead = node;
            }else{
                //头插法创建新链表
                ListNode temp = newHead;
                node.next = temp;
                newHead = node;
            }
            //迭代
            cur = cur.next;
        }
        //返回结果
        return newHead;
    }
}

优化

class Solution {
    public ListNode reverseList(ListNode head) {
        //创建反转链表的头
        ListNode newHead = null;
        //获取当前插入结点
        ListNode cur = head;
        while(cur != null){
            //记录当前结点的后面的结点，以防后面节点被污染
            ListNode next = cur.next;
            //头插法建立链表
            cur.next = newHead;
            newHead = cur;
            //迭代 即 cur = cur.temp;
            cur = next;
        }
        //返回头节点
        return newHead;
    }   
}

图解：

5.2.2 递归

方式1

class Solution {
    public ListNode reverseList(ListNode head) {
        //终止条件
        if(head == null) return null;
        if(head.next == null) return head;

        //单层递归逻辑
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        //返回结果
        ListNode newHead;
    }
}

方式2

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    //从前向后翻转相邻两个节点的指针指向
    public ListNode reverse(ListNode pre,ListNode cur){
        //判断特殊情况
        if(cur == null) return pre;

        //单层递归逻辑
        ListNode temp = cur.next;
        cur.next = pre;

        //返回结果
        return reverse(cur,temp);
    }
}

6.24. 两两交换链表中的节点

LeetCode标签：中等

6.1 题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

6.2 题解

6.2.1 迭代

图解：

6_1

代码：

class Solution {
    public ListNode swapPairs(ListNode head) {
        //创建新的头节点
        ListNode newHead = new ListNode(0,head);
        //创建指针用于记录要交换的两个结点的前一个结点
        ListNode pre = newHead;
        //开始迭代
        while(pre.next != null && pre.next.next != null ){
            //记录临时结点
            ListNode temp1 = pre.next;
            ListNode temp2 = pre.next.next.next;

            //开始交换
            //步骤1
            pre.next = pre.next.next;
            //步骤2
            pre.next.next = temp1;
            //步骤3
            temp1.next = temp2;
            
            //更新迭代指针
            pre = pre.next.next;
        }
        return newHead.next;
    }
}

6.2.2 递归

class Solution {
    //递归法 三步走
    //确定形参和返回值
    public ListNode swapPairs(ListNode head) {
        //确定终止条件
        if(head == null || head.next == null) return head;

        //确定单层递归逻辑

        //步骤1 
        ListNode newHead = head.next;
        //步骤2  进行递归
        head.next = swapPairs(newHead.next);
        //步骤3 
        newHead.next = head;

        return newHead;
    }
}

7.160. 相交链表

LeetCode标签：简答

7.1 题目描述

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

图示两个链表在节点 c1 开始相交：

题目数据保证整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
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 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

7.2 题解

此题的方法都是迭代法

7.2.1 方法1 - 哈希表

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //借助集合
        Set<ListNode> set = new HashSet<>();
        //迭代链表
        ListNode cur = headA;
        while(cur != null){
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while(cur != null){
            if(set.contains(cur)) return cur;
            cur = cur.next;
        }
        return null;
    }
}

7.2.2 方法2 - 双指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //创建变量用于记录两个链表的长度
        int lenA = 0;
        int lenB = 0;
        //开始计算链表长度
        ListNode temp = headA;
        while(temp != null){
            lenA++;
            temp = temp.next;
        }
        temp = headB;
        while(temp != null){
            lenB++;
            temp = temp.next;
        }

        //将长的链表迭代到和短的链表的长度一样结点位置
        if(lenA > lenB){
            for(int i=0;i<lenA-lenB;i++){
                headA = headA.next;
            }
        }else{
            for(int i=0;i<lenB-lenA;i++){
                headB = headB.next;
            }
        }

        //创建变量用于记录答案
        ListNode node = null;
        //开始判断后面的序列是否相等
        while(headA != null){
            if(headA == headB){
                node = headA;
                break;
            }
            headA = headA.next;
            headB = headB.next;
        }

        return node;
    }
}

7.2.3 方法3

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // p1 指向 A 链表头结点，p2 指向 B 链表头结点
		ListNode p1 = headA, p2 = headB;
		while (p1 != p2) {
			// p1 走一步，如果走到 A 链表末尾，转到 B 链表
            p1 = p1 == null ? headB : p1.next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            p2 = p2 == null ? headA : p2.next;
		}
		return p1;
    }
}

算法逻辑：如果两个链表相交，那么相交点之后的长度是相同的，我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。为此，我们必须消除两个链表的长度差
1. 指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
2. 如果 pA 到了末尾，则 pA = headB 继续遍历
3. 如果 pB 到了末尾，则 pB = headA 继续遍历
4. 比较长的链表指针指向较短链表head时，长度差就消除了
5. 如此，只需要将最短链表遍历两次即可找到位置
看完上面的文字和代码，看到这个代码的时候可能你也和毛毛张一样惊讶这么简单！但是你看完之后可能还是不是很理解，下面就来结合图示来看一下吧！

相交链表.png

复杂度分析：

时间复杂度： $O(m+n)$，其中$m$和$n$分别是链表$headA$和$headB$的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次
空间复杂度： $O(1)$

8.141. 环形链表

LeetCode标签：简单

8.1 题目描述

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

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

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

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

提示：

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

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

8.2 题解

方法1 - 哈希表

public class Solution {
    public boolean hasCycle(ListNode head) {
        //遍历的过程中记录遍历过的结点
        //如果出现相等的结点，就可以判定链表中存在环
        ListNode cur = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (cur != null) {
            if (visited.contains(cur)) {
                return true;
            } else {
                visited.add(cur);
            }
            cur = cur.next;
        }
        return false;
    }
}

方法2 - 迭代 - 快慢指针

这种解法的逻辑是小时候的追及与相遇问题的逻辑，假设兔子的速度永远大于乌龟的速度，且兔子不会停，那么在一段笔直的路上，兔子和乌龟永远不会相遇

public class Solution {
    public boolean hasCycle(ListNode head) {
        //快指针
        ListNode fast = head;
        //慢指针
        ListNode slow = head;
        //开始迭代
        while(fast != null && fast.next != null){
            //快指针走两步
            fast = fast.next.next;
            //慢指针走一步
            slow = slow.next;
            //如果两个指针相遇则说明有环
            if(fast == slow){
                return true;
            }
        }
        //对应三种情况：
        //1.链表为空
        //2.链表只有一个结点
        //3.链表没有环
        return false;
    }
}

9.142. 环形链表 II

LeetCode标签：中等

9.2 题目描述

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

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

不允许修改 链表。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

示例 3：

1
2
3

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

提示：

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

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

9.2 题解

方法1 - 哈希表

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //遍历的过程中记录遍历过的结点
        //如果出现相等的结点，就可以判定链表中存在环
        ListNode cur = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (cur != null) {
            if (visited.contains(cur)) {
                return cur;
            } else {
                visited.add(cur);
            }
            cur = cur.next;
        }
        return null;
    }
}

方法2 - 迭代 - 快慢指针

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //快指针
        ListNode fast = head;
        //慢指针
        ListNode slow = head;
        //开始迭代
        while(fast != null && fast.next != null){
            //快指针走两步
            fast = fast.next.next;
            //慢指针走一步
            slow = slow.next;
            //如果两个指针相遇则说明有环
            if(fast == slow){
                ListNode index1 = fast;
                ListNode index2 = head;
                //两指针，从头节点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while(index1 != index2){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        //对应三种情况：
        //1.链表为空
        //2.链表只有一个结点
        //3.链表没有环
        return null;
    }
}

10.总结

链表应该是我们接触数据结构的第一种比较复杂的数据结构，上面毛毛张分享了关于链表的8道题目，并且都尽量从迭代法和递归法的角度分享的解法
关键点：
- 如果在关于链表的删除和增加操作中，如果使用迭代法，经常使用到双指针，找到要删除的结点的前面一个结点比较关键
- 如果使用递归法，通常是递归到链表的底部，从链表的底部执行操作，大家可以仔细体会一下第3道、第4道题目

参考文献

LeetCode官网
代码随想录官网