数据结构与算法刷题之【链表】篇

文章目录

前言
基本概念
剑指offer
剑指 Offer 06. 从尾到头打印链表【简单】
剑指 Offer 18. 删除链表的节点【简单】
牛客
简单
判断表中是否有环【简单】
链表中倒数最后k个结点【简单】
两个链表的第一个公共结点【简单】
判断一个链表是否为回文结构【简单】
删除有序链表中重复的元素-I【简单】
中等
链表内指定区间反转【中等】
删除链表的倒数第 n 个结点（【中等】，牛客/第3题的升级版）
链表中的两数相加【中等】
单链表的排序【中等，三种方案包含哨兵、归并排序，只有归并排序在leetcode不超时】
链表中环的入口结点【中等】
删除有序链表中重复的元素-II【中等】
leetcode
简单
反转链表【简单】
合并两个排序列表【简单】
回文链表【简单】
141. 环形链表【简单】
142. 环形链表 II【中等】
移除链表元素【简单】
中等
160. 相交链表【中等】
2. 两数相加【中等】
奇偶链表【中等】
707. 设计链表【中等】
24. 两两交换链表中的节点【中等】
困难
K 个一组翻转链表【困难】
合并K个排序链表【困难】

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》...有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

基本概念

链表节点

//链表节点定义
class ListNode{
    private int val;
    private ListNode listNode;

    ListNode(int val){
        this.val = val;
    }
}

删除操作时间复杂度O(1)

查找某个节点的时间复杂度O(n)

数组与链表：

数组：插入、删除时间复杂度为O(n)，查询O(1)，适用于频繁查询。数组长度一般为固定。
链表：插入、删除时间复杂度为O(1)，查询O(n)，适用于频繁增删。链表长度一般不固定。

剑指offer

剑指 Offer 06. 从尾到头打印链表【简单】

题目链接：剑指 Offer 06. 从尾到头打印链表

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

解法：

1、反转链表+遍历

复杂度分析：

时间复杂度：O(n)，实际上是2n
空间复杂度：O(n)，集合n+数组n，也是2n

class Solution {
    public int[] reversePrint(ListNode head) {
        //反转链表
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //遍历一遍链表
        List<Integer> res = new ArrayList<>();
        while (pre != null) {
            res.add(pre.val);
            pre = pre.next;
        }
        int[] resArr = new int[res.size()];
        for (int i = 0; i < resArr.length; i++) {
            resArr[i] = res.get(i);
        }
        return resArr;
    }
}

2、双遍历：对比1中在空间复杂度上作了优化

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        int n = 0;
        while (cur != null) {
            n++;
            cur = cur.next;
        }
        //开启数组
        int[] res = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            res[i] = head.val;
            head = head.next;
        }
        return res;
    }
}

剑指 Offer 18. 删除链表的节点【简单】

题目链接：剑指 Offer 18. 删除链表的节点

题目内容：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。

思路：

1、定义虚拟结点，来进行指定删除。

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode temp = new ListNode(-1);
        temp.next = head;
        ListNode pre = temp;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
                cur = pre.next;
                break;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return temp.next;
    }
}

牛客

简单

判断表中是否有环【简单】

题目地址：BM6 判断链表中是否有环

题目：判断给定的链表中是否有环。如果有环则返回true，否则返回false。

思路1：哈希表

存储到一个hash表中来不断进行判断是否有环。（牛客网中提交报语法错误，不理解）
set的添加方法是add。

时间复杂度O(N)：其中 N 为链表中节点的数目。遍历整个链表的结点

空间复杂度O(N)：其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

public boolean hasCycle(ListNode head) {
    ListNode pos = head;
    // 哈希表记录访问过的结点
    Set<ListNode> visited = new HashSet<ListNode>();
    while (pos != null) {
        // 判断结点是否被访问
        if (visited.contains(pos)) {
            return true;
        } else {
            // 结点记录添加到哈希表中
            visited.add(pos);
        }
        // 遍历
        pos = pos.next;
    }
    return false;
}

思路2：双指针(推荐)。

定义一个快指针，一个慢指针，快指针走两步，慢指针走一步，若是快指针过程中碰到null了那么就表示没有环，在移动的过程中一旦快慢指针相等，那么就表示链表成环。

时间复杂度O(N)：其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度

空间复杂度O(1)：额外使用的指针占用常数空间

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

链表中倒数最后k个结点【简单】

题目地址：链表中倒数最后k个结点

题目描绘：输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。如果该链表长度小于k，请返回一个长度为 0 的链表。

思路1（推荐）：返回为0，则表示返回null。我们使用快慢指针来进行移动，快的先移动k个，之后双方同时向后移动。

时间复杂度O(N)：N为链表长度，遍历整个链表

空间复杂度O(1)：使用额外常数大小空间

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        //双指针
        ListNode temp = new ListNode(-1);
        temp.next = pHead;
        ListNode slow = temp;
        ListNode fast = temp;
        //先让快指针移动
        for(int i = 0; i < k; i++) {
            if (fast != null) {
                fast = fast.next;
            }
        }
        //边界问题：若是倒数k个数超过范围了，返回null
        if (fast == null) {
            return null;
        }
        //同时向后移动
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

思路2：通过栈数据结构，先入栈，后出栈k个。

时间复杂度O(N)：N为链表长度，遍历整个链表

空间复杂度O(N)：使用额外常数大小空间

两个链表的第一个公共结点【简单】

题目地址：两个链表的第一个公共结点

题目描述：输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路1：利用哈希表来定位公共结点

时间复杂度O(N)：N为链表长度，遍历整个链表

空间复杂度O(N)：使用额外常数大小空间

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //思路：利用哈希表来解决
        Set<ListNode> visited = new HashSet<ListNode>();
        //遍历headA添加结点到set中
        while (headA != null) {
            visited.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (visited.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

思路2：念念不忘，必有回想，通过从另一个他路径上不断寻找

时间复杂度O(N)：N为链表长度，遍历整个链表

空间复杂度O(1)：使用额外常数大小空间

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB ==null ) {
        return null;
    }
    //定义两个结点
    ListNode n1 = headA;
    ListNode n2 = headB;
    while (n1 != n2) {
        n1 = n1 == null ? headB : n1.next;
        n2 = n2 == null ? headA : n2.next;
    }
    return n1;
}

判断一个链表是否为回文结构【简单】

题目链接：判断一个链表是否为回文结构

题目内容：给定一个链表，请判断该链表是否为回文结构。

思路1：双指针+反转链表

后半部分反转，以后半部分为null作为结束比对条件。

时间复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    public boolean isPail (ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }
        //定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        //奇数情况
        if (fast != null) {
            slow = slow.next;
        }
        //后半部分链表进行反转
        ListNode right = reverse(slow);
        //回文比较
        while (right != null) {
            if (right.val != head.val) {
                return false;
            }
            right = right.next;
            head = head.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = dummy;
            dummy = head;
            head = temp;
        }
        return dummy;
    }
    
}

删除有序链表中重复的元素-I【简单】

题目链接：删除有序链表中重复的元素-I

题目内容：删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次。

思路1：使用Set容器来进行判重操作。

时间复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        Set<Integer> sets = new HashSet<>();
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            //判断是否在容器中出现
            if (!sets.contains(cur.val)) {
                sets.add(cur.val);
                pre = cur;
            }else {
                //删除节点动作
                pre.next = cur.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

思路2：遍历删除

注意题目是有序，那么我们无需考虑乱序的一个情况。

时间复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            //遍历到不相等的元素
            while (temp != null && temp.val == cur.val) temp = temp.next;
            cur.next = temp;
            cur = cur.next;
        }
        return head;
    }
}

中等

链表内指定区间反转【中等】

题目地址：BM2 链表内指定区间反转

题目描述：将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。

思路：

    /**
     * 思路：起始位定位，翻转指定区间链表，需要临时保存的结点有：初始定位前置结点以及初始结点，方便反转后进行连接。
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        //到达要反转的链表节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode reverseHeadPre = null;//反转前头结点的前置结点
        ListNode reverseTail = null;//反转后链表的末尾结点
        ListNode cur = dummy;//反转后的头结点
        n = n - m + 1;
        while (m != 0) {
            if (m == 1) {
                reverseHeadPre = cur;//保存前置结点
            }
            cur = cur.next;
            m--;
        }
        //进行反转链表
        reverseTail = cur;//临时保存下链表反转后的末尾结点
        ListNode pre = null;
        while (n != 0) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
            n--;
        }
        reverseTail.next = cur;
        reverseHeadPre.next = pre;
        return dummy.next;
    }

删除链表的倒数第 n 个结点（【中等】，牛客/第3题的升级版）

题目地址：删除链表的倒数第 n 个结点

题目描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

思路1：首先定位到对应的倒数第k个结点，接着再此基础上加上一个前缀结点，用于之后进行删除操作，即可AC。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode temp = new ListNode(-1);
        temp.next = head;
        //定义快慢指针
        ListNode slow = temp;
        ListNode fast = temp;
        ListNode pre = null;
        //快指针先走
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //同时走
        while (fast != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre.next = slow.next;
        return temp.next;
    }
}

链表中的两数相加【中等】

题目链接：链表中的两数相加

题目内容：假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。给定两个这种链表，请生成代表两个整数相加值的结果链表。

思路1：使用两个栈来进行操作，依次相加并最终组成链表返回。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // 937 
        //  63
        //1000
        //筛选情况
        if (head1 == null) {
            return head2;
        }
        if (head2 == null) {
            return head1;
        }
        //链表转为栈
        Stack<ListNode> s1 = new Stack<>();
        Stack<ListNode> s2 = new Stack<>();
        while (head1 != null) {
            s1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            s2.push(head2);
            head2 = head2.next;
        }
        //处理进位情况
        int tmp = 0;
        ListNode head = new ListNode(-1);
        ListNode nHead = head.next;
        //只要任意一个栈有元素即可
        while (!s1.isEmpty() || !s2.isEmpty()) {
            //求得一个相加值
            int val = tmp;
            if (!s1.isEmpty()) {
                val += s1.pop().val;
            }
            if (!s2.isEmpty()) {
                val += s2.pop().val;
            }
            tmp = val / 10;
            ListNode node = new ListNode(val % 10);
            node.next = nHead;
            nHead = node;
        }
        //处理tmp>0最终情况
        if (tmp > 0) {
            ListNode node = new ListNode(tmp);
            node.next = nHead;
            nHead = node;
        }
        return nHead;
    }
}

单链表的排序【中等，三种方案包含哨兵、归并排序，只有归并排序在leetcode不超时】

题目链接：单链表的排序

题目内容：给定一个节点数为n的无序单链表，对其按升序排序。

思路1：对链表进行选择排序，仅仅只是交换结点的值（超时）

时间复杂度O(n)

空间复杂度O(1)

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //选择排序：交换结点中的值
        ListNode move  = head;
        while (move != null) {
            ListNode temp = move.next;
            while (temp != null) {
                if (move.val > temp.val) {
                    int tmp = move.val;
                    move.val = temp.val;
                    temp.val = tmp;
                }
                temp = temp.next;
            }
            move = move.next;
        }
        return head;
    }
}

思路2：交换结点。【leetcode超时】

1.建立哨兵节点
2.每次从未排序的链表节点中找出最小的节点接到已排序链表的后面

时间复杂度O(n)

空间复杂度O(1)

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //定义一个虚拟结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //定义一个哨兵结点
        ListNode sentryNode = dummy;
        //若是哨兵的下一个结点为null，那么不继续往下执行
        while (sentryNode.next != null) {
            ListNode pre = sentryNode;
            ListNode cur = sentryNode.next;
            ListNode minPre = null;
            ListNode min = null;
            //来找出最小结点
            while (cur != null) {
                //比较取得最小值
                if (min == null || min.val > cur.val) {
                    min =  cur;
                    minPre = pre;
                }
                pre = pre.next;
                cur = cur.next;
            }
            //此时已经找到最小结点，来依靠哨兵结点进行交接对换
            minPre.next = min.next;
            min.next = sentryNode.next;
            sentryNode.next = min;
            sentryNode = min;
        }
        return dummy.next;
    }
}

思路3：归并排序

时间复杂度O(nlogn)

空间复杂度O(1)

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        //若是当前只有一个结点，那么直接返回该结点即可
        if (head == null || head.next == null) {
            return head;
        }
        //找到中间点，定义快慢指针
        ListNode slow = head;
        ListNode fast = head.next;//若是fast结点不设置为head.next那么就会进入到死循环中
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        //递归左右两边来进行比较操作
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);
        //开始进行合并操作
        ListNode res = new ListNode(-1);
        ListNode dummy = res;
        while (left != null && right != null) {
            if (left.val < right.val) {
                dummy.next = left;
                left = left.next;
            }else {
                dummy.next = right;
                right = right.next;
            }
            dummy = dummy.next;
        }
        dummy.next = left != null ? left : right;
        return res.next;
    }
}

问题：为什么fast=head.next，设置为fast=head就会出现栈溢出？

核心就是出现了无限递归调用的情况了，这里举个例子就明白了：

例如：5->4->null

head为5结点

接着fast、slow一轮下来之后，slow为结点4，此时调用sortInList(head)，此时head依旧是5结点

那么下一次同样也是5->4->null，此时就会出现无限递归调用了！

链表中环的入口结点【中等】

题目链接：链表中环的入口结点

题目内容：给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

思路1：①判断是否为环形。②若是环形，从相遇点以及链表初始点同时出发n个位置相等时的结点即为入口结点。

时间复杂度分析：

时间复杂度：O(n)
空间复杂度：O(1)

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    public ListNode hasCircular(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }
        //定义快慢指针
        ListNode slow = pHead;
        ListNode fast = pHead;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //判断是否有环
        ListNode node = hasCircular(pHead);
        if (node == null) {
            return null;
        }
        //若是不为null，表示有环，从环中点与起点同时出发相遇的点即可入口结点
        ListNode node2 = pHead;
        while (node2 != node) {
            node2 = node2.next;
            node = node.next;
        }
        return node2;
    }
}

删除有序链表中重复的元素-II【中等】

题目链接：删除有序链表中重复的元素-II

题目内容：给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。

思路1：通过一个计数器来判断重复

时间复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        ListNode h = dummy;
        //基准比较结点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            //重复检测动作
            fast = fast.next;
            int num = 0;
            while (fast != null && fast.val == slow.val) {
                num++;
                fast = fast.next;
            }
            //表示出现了重复情况
            if (num > 0) {
                if (fast == null)
                    break;
                slow = fast;
                fast = fast;
                continue;
            }
            //添加到新的结点
            h.next = new ListNode(slow.val);
            h = h.next;
            if (slow != null) {
                 //两个指针也要移动
                slow = slow.next;
            }
        }
        return dummy.next;
    }
}

思路2：重复值变量表示，之后重复比较即可

优化思路1，空间复杂度O(n)优化为O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode deleteDuplicates (ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = dummy;
        //保证后面有两个结点存储，满足可能出现重复值情况
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int temp = cur.next.val;
                //遍历判断重复的值
                while (cur.next != null && cur.next.val == temp) {
                    //删除重复值的结点
                    cur.next = cur.next.next;
                }
            }else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}

leetcode

简单

反转链表【简单】

题目链接：剑指 Offer II 024. 反转链表

题目描述：给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

思路：①定义一个前置节点，之后配合前后指针进行移动来进行反转，最终返回前置节点。

方式一：非递归

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

方式二：递归

// 方式二：采用递归写法
/**
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41.2 MB, 在所有 Java 提交中击败了36.33%的用户
     */
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);
}

合并两个排序列表【简单】

链接地址：剑指 Offer 25. 合并两个排序的链表

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

思路解法：定义一个新节点，并且设置虚拟头结点，接着对两个链表进行依次比较连接。

方式一：非递归反转

/**
 * 思路：定义一个新节点，并且设置虚拟头结点，接着对两个链表进行依次比较连接。
 * 时间复杂度O(n)，空间复杂度O(n)
 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
 * 内存消耗：41.2 MB, 在所有 Java 提交中击败了63.20%的用户
 */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            cur.next = new ListNode(l1.val);
            l1 = l1.next;
        }else {
            cur.next = new ListNode(l2.val);
            l2 = l2.next;
        }
        cur = cur.next;
    }
    //处理链表剩余节点
    while (l1 != null) {
        cur.next = new ListNode(l1.val);
        l1 = l1.next;
        cur = cur.next;
    }
    while (l2 != null) {
        cur.next = new ListNode(l2.val);
        l2 = l2.next;
        cur = cur.next;
    }
    return dummy.next;
}

方式二：递归处理，不断比较两个值并且返回对应的链表

//方式二：递归解法
/**
     * 思路：每个子问题都是比较两个值得大小，最终返回一个已经排好序的链表
     * 
     * 时间复杂度O(n)，空间复杂度O(1)
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40.9 MB, 在所有 Java 提交中击败了37.67%的用户
     */
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }else if (l2 == null) {
        return l1;
    }else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    }else{
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

回文链表【简单】

链接地址：234. 回文链表

题目描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

方式一：添加集合比较法

思路：将链表中所有的结点添加到数组中，然后进行比较。

/**
 * @ClassName 回文链表【简单】
 * @Author ChangLu
 * @Date 4/26/2022 6:07 PM
 * @Description 回文链表：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 地址：https://leetcode-cn.com/problems/palindrome-linked-list/
 */
public class 回文链表 {
    //方式一：全部添加到集合中，然后依次比较
    /**
     * 时间复杂度O(n)，空间复杂度O(n)
     * 执行用时：6 ms, 在所有 Java 提交中击败了51.96%的用户
     * 内存消耗：53.6 MB, 在所有 Java 提交中击败了70.35%的用户
     */
    public boolean isPalindrome(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();
        while (head != null) {
            nodes.add(head);
            head = head.next;
        }
        //来进行依次比对
        int left = 0;
        int right = nodes.size() - 1;
        while (left < right) {
            if (nodes.get(left).val != nodes.get(right).val) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

方式二：快慢指针+反转链表

思路：使用快慢指针来进行遍历链表，过程中利用慢指针来进行反转一半链表结点，最终来进行比对。

 //方式二：快慢指针+链表反转，最终进行回文比对
/**
     * 时间复杂度O(n),空间复杂度O(1)
     * 执行用时：3 ms, 在所有 Java 提交中击败了99.10%的用户
     * 内存消耗：57.4 MB, 在所有 Java 提交中击败了49.65%的用户
     */
public boolean isPalindrome(ListNode head) {
    //定义快慢指针
    ListNode slow = head;
    ListNode fast = head;
    ListNode cur = slow;//根据慢指针来进行不断反转
    ListNode pre = null;
    //在慢指针移动时顺便反转一半链表
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        cur.next = pre;
        pre = cur;
        cur = slow;
    }
    //奇数情况
    if (fast != null) {
        slow = slow.next;
    }

    //最后进行对比比较值：pre与slow
    while (pre != null) {
        if (pre.val != slow.val) {
            return false;
        }
        pre = pre.next;
        slow = slow.next;
    }
    return true;
}

141. 环形链表【简单】

学习：leetcode题解

题目链接：141. 环形链表

题目内容：

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

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

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

速记：

①哈希表：使用set将每个链表节点进行存储，若是遍历过程中添加失败，则说明有环；若是过程中碰到为null的节点，则说明无环。
②快慢指针：快指针走两步，慢指针走一步。以快慢指针指向节点是否相同来作为判断条件，若是相同则说明有环，若是中途指针指向有null，则说明无环。

思路：

1、哈希表

思路：将每一个链表节点都进行临时存储，遍历下一个节点的时候都尝试插入到哈希表中，若是插入成功说明没有碰到相同的节点，若是失败则表明有环。

复杂度分析：时间复杂度O(n)，空间复杂度O(n)

public boolean hasCycle(ListNode head) {
    //哈希表
    Set<ListNode> sets = new HashSet<>();
    while (head != null){
        if (!sets.add(head)){
            return true;
        }
        head = head.next;
    }
    return false;
}

2、快慢指针

思路：使用两个指针，一个慢一个快，以两个指针指向节点是否相等来作为条件，若是相等则说明有环，若是遍历过程中若是为null，则表示无环已经走到底了，直接结束。

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        //定义快慢指针
        ListNode slow = head;
        ListNode fast = slow.next;
        //设置快慢指针是否相同作为条件
        while (slow != fast){
            //让快指针来进行探路判断
            if (fast == null || fast.next == null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}

142. 环形链表 II【中等】

学习：leetcode题解、代码随想录—142.环形链表II

题目链接：142. 环形链表 II

题目内容：

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

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

核心问题：

1、为什么慢指针一定会与快指针重合相遇？

快指针每次移动2步，慢指针移动1步，慢指针与快指针必会重合。不同情况的环快指针可能会走n圈，慢指针不会超过一圈。也就是说一圈内必重合。

2、求解到相遇的节点之后，如何确定指定的入环节点？

这里我觉得代码随想录—题解中的图特别好这里引用一下：

慢指针走的步数：x+y

快指针走的步数：x+y+n(z+y)，这里z+y指的是环形一圈的意思，n指的是转了n圈。

因为快指针每次走两步，慢指针走一步，公式：2(x+y) = x+y+n(z+y) => x+y = n(z+y) => x = n(z+y)-y

最终化解为：x = (n-1)(z+y)+z，(n-1)(z+y)就是指的快指针环形绕的n圈意思

此时我们可以得出一个结论，当快慢指针相遇时，x与z的值都是相等的，那么我们代码中只需要求得快慢指针重合的节点以及头节点每次移动一步进行对比即可找出环形入口节点。

注：主要是看了代码随想录—题解思路再进行自己归纳总结了下。

思路：

1、快慢指针

思路：快慢指针(慢一步，快两步)，找到环内重合点，接着令头节点与重合节点一起移动，每次移动一步，一旦两个指针指向的节点相同就找到入环节点

public ListNode detectCycle(ListNode head) {
    //节点为null、1个节点直接返回null
    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 index1 = head;
            ListNode index2 = fast;
            //结合之前等式，我们来进行同时移动两个指针每次移动一步，一旦相等就说明找到了入环节点
            while(index1 != index2){
                index1 = index1.next;
                index2 = index2.next;
            }
            return index1;//此时返回任意一个节点即可，因为此时是index1与index2都是相同节点
        }
    }
    return null;
}

移除链表元素【简单】

学习：203.移除链表元素

题目链接：leetcode—移除链表元素

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

思路：

1、暴力解法

思路：设置一个新链表节点，遍历原有链表，一旦不符合的数字就进行赋值

中间有多次出现案例错误问题，最终解决。

/**
  * 移除链表元素
  * @param head
  * @param val
  * @return
  */
public ListNode removeElements(ListNode head, int val) {
    //头节点为null或者头节点的next节点为null以及当前节点==val，返回null
    if(head == null || (head.next == null && head.val == val)){
        return null;
    }
    //新节点
    ListNode newHeadNode = null;
    //处理第一个节点
    if(head.val != val){
        newHeadNode = new ListNode(head.val,null);
    }
    ListNode curNode = newHeadNode;
    //nextNode表示下一节点
    ListNode nextNode = head.next;
    //遍历下面的每一个节点
    while(nextNode!=null){
        if(nextNode.val != val){
            if(newHeadNode == null){
                newHeadNode = new ListNode(nextNode.val,null);
                curNode = newHeadNode;
            }else{
                curNode.next = new ListNode(nextNode.val,null);;
                curNode = curNode.next;
            }
        }
        nextNode = nextNode.next;
    }
    return newHeadNode;
}

2、设置虚拟节点方案

//设置虚拟节点
public ListNode removeElements(ListNode head, int val) {
    //节省内存消耗，这里可以提前结束方法
    if(head == null){
        return null;
    }
    ListNode dummy = new ListNode(-1,head);
    ListNode pre = dummy;//前置节点
    ListNode cur = head;//循环遍历的节点
    while(cur!=null){
        if(cur.val == val){
            pre.next = cur.next;  //相当于删除当前节点
        }else{ 
            pre = cur; //移动对应的前置节点
        }
        cur = cur.next;
    }
    return dummy.next;
}

不设置虚拟节点方案：

//不设置虚拟节点
public ListNode removeElements(ListNode head, int val) {
    //筛减掉不符合的元素
    while(head!=null && head.val == val){
        head = head.next;
    }
    if(head == null){
        return null;
    }
    //当前head.val != val，我们下面可以直接对next进行遍历操作
    ListNode pre = head;
    ListNode cur = head.next;
    while( cur != null){
        if(cur.val == val){
            pre.next = cur.next;  //相当于删除操作
        }else{
            pre = cur;
        }
        cur = cur.next;
    }
    return head;
}

总结：其实后来的两种方式也大差不差，无非一个是通过创建一个虚拟节点，另一个在原有head节点上做文章，核心还是在对链表的遍历这里，通过设置一个虚拟节点我觉得效果更好。

中等

160. 相交链表【中等】

学习：leetcode题解

题目链接：160. 相交链表

题目内容：

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

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

速记：

①首先求得两个链表的长度，根据长度差值将长的指针向后移动，直至两个链表从相同长度开始来进行一一比较得出相交结点。
②使用哈希表来先存储链表A的所有节点，接着对链表B进行遍历，若是B的某个节点在哈希表中存在，那么就说明相交。
③使用两个指针来同时遍历两个链表，两个指向指向的节点是否相等作为条件，若是某个链表先遍历完了还没找到，那么就让该节点从新的链表出发，另一个节点同理。最终只有两种情况，①相交。②无相交，最终同时会指向null结束。

思路：

1、同步后缀比较

思路：首先求得两个链表的长度，根据长度差值将长的指针向后移动，直至两个链表从相同长度开始来进行一一比较得出相交结点。

复杂度分析：时间复杂度O(n)，空间复杂度O(1)

class Solution {

    /**
     * 获取链表的长度
     * @param node
     * @return
     */
    public int getListNodeSize(ListNode node){
        int size = 0;
        while (node != null){
            size++;
            node = node.next;
        }
        return size;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        //确定链表的长度
        int aSize = getListNodeSize(headA);
        int bSize = getListNodeSize(headB);
        //移动节点少的链表，让其成为相同长度的链表
        int moveSize = Math.abs(aSize-bSize);
        if(aSize < bSize){
            while (moveSize-- > 0){
                headB = headB.next;
            }
        }else if(aSize > bSize){
            while (moveSize-- > 0){
                headA = headA.next;
            }
        }

        //开始正式比对
        while(headA != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
}

2、哈希集合

思路：首先将链表A的节点全部存储到哈希集合中，之后遍历链表B来查看在哈希集合中是否存在对应的节点A。

复杂度分析：时间复杂度O(m+n)，空间复杂度O(m)

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null){
        return null;
    }
    Set<ListNode> nodes = new HashSet<>();
    while (headA != null){
        nodes.add(headA);
        headA = headA.next;
    }

    //遍历headB链表，来判断是否有相交的节点
    while (headB != null){
        if(nodes.contains(headB)){
            return headB;
        }
        headB = headB.next;
    }
    return null;
}

3、双指针

思路：两个链表长度分别为m、n。两个链表同时从头节点出发，若是先碰到节点，则将该指针指到另一个链表的头节点继续两个指针向后移动，另外一个节点也是如此。最终会有两个结果：①没有交点，最终都会为null，直接结束。②有交点，两个节点相等。

复杂度分析：时间复杂度O(m+n)，空间复杂度O(1)

class Solution {
    //双指针思路
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode pA = headA;
        ListNode pB = headB;
        //最终会有两种情况：①没有交点，最终都会为null，直接结束。②有交点，两个节点相等。
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

2. 两数相加【中等】

学习：leetcode题解

题目链接：2. 两数相加

题目内容：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

思路：

1、模拟（虚拟头节点）

思路：定义虚拟头节点，接着两个链表进行统一位置值相加，过程中需要使用一个temp来保存是否/10的结果(即进一)。

复杂度分析：时间复杂度O(max(m,n))、空间复杂度O(1)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode root = new ListNode(-1);
    ListNode cur = root;
    int temp = 0;
    while (l1 != null && l2 != null) {
        int sum = temp + l1.val + l2.val;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        temp = sum / 10;
        l1 = l1.next;
        l2 = l2.next;
    }

    //将剩余节点进行补充
    fillListNode(l1, cur, temp);
    fillListNode(l2, cur, temp);

    //两个链表相同长度
    if (l1 == null && l2 == null && temp == 1) {
        cur.next = new ListNode(1);
    }
    return root.next;
}

public void fillListNode(ListNode node,ListNode cur,int temp){
    if (node == null){
        return;
    }
    while (node != null){
        int sum = temp + node.val;
        cur.next = new ListNode(sum % 10);
        cur = cur.next;
        temp = sum / 10;
        node = node.next;
    }
    if (temp == 1) {
        cur.next = new ListNode(1);
    }
}

2、模拟（优化代码）

思路：与NO1思路一致，只不过这里并没有定义虚拟头节点，代码结构也更加清晰。

复杂度分析：时间复杂度O(max(m,n))、空间复杂度O(1)

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    int temp = 0;
    ListNode head = null, tail = null;
    while (l1 != null || l2 != null) {
        //取得两个链表的当前位置的值
        int val1 = l1 != null ? l1.val : 0;
        int val2 = l2 != null ? l2.val : 0;
        int sum = temp + val1 + val2;
        //头节点构造情况及之后尾部添加
        if (head == null) {
            head = tail = new ListNode(sum % 10);
        }else{
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        //保存十位数位置值(是否进1)
        temp = sum / 10;
        if (l1 != null){
            l1 = l1.next;
        }
        if (l2 != null){
            l2 = l2.next;
        }
    }
    if (temp > 0) {
        tail.next = new ListNode(temp);
    }
    return head;
}

奇偶链表【中等】

链接地址：328. 奇偶链表

题目描述：给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。

方式一：奇偶链表，寻路链表，最后拼接

//方式一：定义奇、偶数链表，使用导航节点来进行指引奇、偶节点进行连接，最后将偶数链表连接到奇数链表末尾返回。
/**
     * 时间复杂度O(n)、空间复杂度O(1)
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40.5 MB, 在所有 Java 提交中击败了91.77%的用户
     */
public ListNode oddEvenList(ListNode head) {
    //若是节点数为0或者1直接返回
    if (head == null || head.next == null) {
        return head;
    }
    //定义奇数节点、偶数节点。对于head节点不动，tail节点不断向后移动
    ListNode oddHead = head;
    ListNode oddTail = oddHead;
    ListNode evenHead = head.next;
    ListNode evenTail = evenHead;
    //定义一个导航节点
    ListNode p = head.next.next;
    while (p != null) {
        //先尝试连接奇数链表
        oddTail = oddTail.next = p;
        p = p.next;
        if (p != null) {
            //连接偶数链表
            evenTail = evenTail.next = p;
            p = p.next;
        }
    }
    //将偶数链表连接到奇数链表末节点之后
    oddTail.next = evenHead;
    evenTail.next = null;//奇数链表末尾是null
    return oddHead;
}

707. 设计链表【中等】

学习：代码随想录—707.设计链表、leetcode评论

题目链接：707. 设计链表

题目内容：

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

注意：

①注意下面这句话，第 index 个节点之前添加值为 val 的节点实际上与后面等于链表的长度不冲突，只需要把等于条件放在前面即可。

addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。

②注意点(坑点)：红框勾选的一个是获取，一个是删除，注意题目写的是获取或删除第index个节点，从字面上来看传入1，就是删除掉链表中的第一个元素，而实际上则是需要你删除或获取到索引为index的元素。

思路：

1、手写链表

看题先自己尝试手写并。期间有N次提交失败，还有空指针异常情况，主要就是我们上面二大注意点提到的，经过一些时间终于AC！

class MyLinkedList {

    private ListNode head;//头节点
    private ListNode tail;//尾结点
    private int size;//节点数量

    class ListNode{
        private int val;
        private ListNode next;

        public ListNode(int val,ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public MyLinkedList() {
        this.size = 0;
    }

    /**
     * 取的是索引
     * @param index
     * @return
     */
    public int get(int index) {
        if(!checkExists(index)){
            return -1;
        }
        //遍历链表
        ListNode cur = this.head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }

    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val, this.head);
        //更新尾结点
        if(this.tail == null){
            this.tail = newHead;
        }
        //更新头节点
        this.head = newHead;
        this.size++;
    }

    public void addAtTail(int val) {
        ListNode newTail = new ListNode(val, null);
        //更新尾结点
        this.tail = newTail;
        //处理无头节点情况
        if(this.head == null){
            this.head = newTail;
        }else{
            //遍历到尾节点插入
            ListNode cur = this.head;
            for (int i = 0; i < this.size-1; i++) {
                cur = cur.next;
            }
            cur.next = newTail;
        }
        this.size++;
    }

    public void addAtIndex(int index, int val) {
        //情况1：index>size，不插入节点
        if(index > this.size){
            return;
        }
        //情况2：index<0，在头部插入节点（包含index=0情况）
        if(index <= 0){
            this.addAtHead(val);
            return;
        }
        //情况3：index=size，添加到链表末尾
        if(index == this.size){
            this.addAtTail(val);
            return;
        }
        //最终情况：在指定index位置前插入
        ListNode newNode = new ListNode(val, null);
        ListNode pre = this.head;
        //当前数量>1，index>1情况，找到前置节点
        for (int i = 1; i < index; i++) {
            pre = pre.next;
        }
        //插入节点操作
        newNode.next = pre.next;
        pre.next = newNode;
        this.size++;
    }

    public void deleteAtIndex(int index) {
        if(!checkExists(index)){
            return;
        }
        //情况1：index=0情况
        if(index == 0){
            this.head = this.head.next;
            if(size == 1){
                this.tail = null; //若是当前数量也为1，尾节点也要删除
            }
            this.size--;
            return;
        }
        //定位到要删除的指定节点前一个
        ListNode cur = head;
        for (int i = 1; i < index; i++) {
            cur = cur.next;
        }
        //判断是否是尾节点，是的话更新尾节点
        if(cur.next == this.tail){
            this.tail = cur;
        }else{
            //删除指定节点
            cur.next = cur.next.next;
        }
        this.size--;
    }

    public boolean checkExists(int index){
        if(index < 0 || index >= size){
            return false;
        }
        return true;
    }

}

2、双向链表

案例参考leetcode题解的某个评论：我是理解了jdk-8 LinkedList源码写出来的有不对的地方，希望指正

使用双向链表的话其实就更加轻松一点，并且在本案例中对于方法重用的设计也更加巧妙！

class MyLinkedList {

    private class Node{
        public int val;
        public Node next;
        public Node prev;
        Node(int val){
            this.val = val;
        }

        Node(Node prev,int val,Node next){
            this.prev = prev;
            this.val = val;
            this.next = next;
        }
    }

    //头节点
    private Node first;
    //尾结点
    private Node last;
    //链表长度
    private int size;

    public MyLinkedList() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }

    public boolean checkIndex(int index){
        if(index<0 || index>=size){
            return false;
        }
        return true;
    }

    public int get(int index) {
        if(!checkIndex(index)){
            return -1;
        }
        if(index == 0){
            return this.first.val;
        }else if(index == this.size-1){
            return this.last.val;
        }else{
            return indexOf(index).val;
        }
    }

    private Node indexOf(int index) {
        //判断当前索引在链表中的大致位置，若是在左边优先从头节点遍历
        if(index < size>>1 ){
            Node cur = this.first;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur;
        }else{//从后向前遍历
            Node cur = this.last;
            for (int i = 1 ;i< this.size-index; i++) {
                cur = cur.prev;
            }
            return cur;
        }
    }

    public void addAtHead(int val) {
        //记录保存一下当前的第一个节点
        Node f = this.first;
        Node newNode = new Node(null, val, f);
        this.first = newNode;//更新一下头节点
        //如果原本第一个节点为null，说明原本链表为空，此时尾结点也肯定为空
        if(f == null){
            this.last = newNode;
        }else{
            f.prev = newNode;//原本的前置节点进行更新
        }
        this.size++;
    }

    public void addAtTail(int val) {
        //记录保存一下当前的尾节点
        Node l = this.last;
        Node newNode = new Node(l, val, null);
        this.last = newNode;//更新一下尾节点
        if(l == null){
            this.first = newNode;
        }else{
            l.next = newNode;//更新一下当前头节点
        }
        this.size++;
    }

    public void addAtIndex(int index, int val) {
        if(index == 0){
            this.addAtHead(val);
        }else if(index == this.size){
            this.addAtTail(val);
        }else if(index>this.size){
            return;
        }else{
            //此时index是在当前链表必存在的情况
            add(index,val);
        }
    }

    public void add(int index, int val) {
        Node cur = indexOf(index);
        Node preNode =  cur.prev;
        Node newNode = new Node(preNode, val, cur);
        //更新索引为index节点的后置节点为新节点
        preNode.next = newNode;
        cur.prev = newNode;
        this.size++;
    }

    public void deleteAtIndex(int index) {
        if(!checkIndex(index)){
            return;
        }
        //当前节点数量=1情况
        if(this.size == 1){
            this.size--;
            this.first = null;
            this.last = null;
            return;
        }
        //当前节点数量>1情况：找到指定要删除的节点
        Node delNode = indexOf(index);
        //删除节点为头节点情况
        if(index == 0){
            this.first = delNode.next;
            this.first.prev = null;
        }else if(index == this.size-1){//为尾结点情况
            this.last = this.last.prev;
            this.last.next = null;
        }else{
            //中间情况，前后节点都要进行更新
            delNode.prev.next = delNode.next;
            delNode.next.prev = delNode.prev;
        }
        this.size--;
    }
}

24. 两两交换链表中的节点【中等】

学习：leetcode题解、代码随想录—24. 两两交换链表中的节点

题目链接：24. 两两交换链表中的节点

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

思路：

1、三指针移动

思路：定义三个指针，每次两两交换后，统一移动三个指针，中间可能会比较绕一点，可搭配画图进行题解。

核心其实就是不断移动三个指针，之后来进行两两交换操作，中间注意一些边界条件即可。

public ListNode swapPairs(ListNode head) {
    //1个或0个节点直接返回
    if(head == null || head.next == null){
        return head;
    }
    //三个指针
    ListNode preNode = null;
    ListNode firstNode = head;
    ListNode secNode = firstNode.next;

    //最终返回的头节点
    ListNode newHead = secNode;

    //只有成对的才能够进行下面的操作
    while(firstNode !=null && secNode != null){
        //保存secNode的后一个节点
        ListNode postNode = secNode.next;
        //反转节点
        secNode.next = firstNode;
        firstNode.next = postNode;
        if(preNode!=null){
            preNode.next = secNode;
        }

        //移动三个指针
        preNode = firstNode;//第一个指针
        if(postNode == null){
            break;
        }
        firstNode = postNode;//第二个指针
        if(postNode.next == null){
            break;
        }
        secNode = postNode.next;
    }

    return newHead;
}

2、虚拟头结点

思路：定义一个虚拟节点后，之后的操作都是相同的，其中核心是以两个指针来进行节点之间的交换。

public ListNode swapPairs(ListNode head) {
    //虚拟节点
    ListNode dummyNode = new ListNode(0, head);
    ListNode preNode = dummyNode;
    //该条件含义指的是：保证当前还有成对的进行反转。下面主要核心就是通过preNode、head两个指针来进行两两反转
    while(preNode.next != null && preNode.next.next != null){
        //临时保存第3个节点，之后反转链表指向第3个节点时有用
        ListNode tempNode =  head.next.next;
        //反转链表节点
        preNode.next = head.next;
        head.next.next = head;
        head.next = tempNode;
        //移动指针 (注意此时的head与已反转)
        preNode = head;
        head = preNode.next;
    }
    return dummyNode.next;
}

3、递归求解

思路：下面针对于递归题解进行部分问题解答

/**
  * 递归
  * @param head
  * @return 上一组交换的下一个目标节点
  */
public ListNode swapPairs(ListNode head) {
    if(head == null || head.next == null){
        return head;
    }
    ListNode next =  head.next;
    ListNode newNode = swapPairs(next.next);
    //反转链表，只负责当前两个节点指向
    next.next = head;
    head.next = newNode;
    return next;
}

困难

K 个一组翻转链表【困难】

【LeetCode 25. K 个一组翻转链表】每天一题刷起来！C++ 年薪冲冲冲！

链接地址：25. K 个一组翻转链表

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

思路解法：反转链表的进阶版，实际上就是遍历一遍的过程中每根据k个来进行翻转一下，在这里一定要定义一个虚拟头节点，并且在过程中需要使用一些额外的其他节点。

方式一：非递归反转

    /**
     * 时间复杂度O(n)，空间复杂度O(1)
     * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：40.7 MB, 在所有 Java 提交中击败了83.91%的用户
     */
    //示例：[1,2,3,4,5] 2
    public ListNode reverseKGroup(ListNode head, int k) {
        if (k <=1 || head == null || head.next == null ) {
            return head;
        }
        ListNode dummy = new ListNode(0);//虚拟头节点
        dummy.next = head;
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            ListNode tail = cur;
            for (int i = 0; i < k; i++) {
                if (tail != null) {
                    tail = tail.next;
                }else {
                    return dummy.next;
                }
            }
            //找到尾节点
            pre.next = reverse(cur, tail);
            cur.next = tail;
            pre = cur;
            cur = tail;
        }
        return dummy.next;
    }

    //反转指定范围的链表
    public ListNode reverse(ListNode head,ListNode tail) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

合并K个排序链表【困难】

相同题目：23. 合并K个升序链表

链接地址：剑指 Offer II 078. 合并排序链表

题目描述：请将所有升序排序的链表合并到一个升序链表中，返回合并后的链表。

方式一：一一比较法

思路：每次来比较所有链表当前第一个元素，找到最小值来连接到新链表后，接着更新该位置链表的当前值，之后不断循环比较即可。

//方式一：比较法
/**
     * 思路：遍历数组，每次找出最小的值连接到dummy结点上，对应的数组位置也进行改变。
     * 学习：https://www.bilibili.com/video/BV1QK4y1N7ww?spm_id_from=333.337.search-card.all.click
     *
     * 时间复杂度0(n*m)，空间复杂度O(1)
     * 执行用时：233 ms, 在所有 Java 提交中击败了5.25%的用户
     * 内存消耗：43.5 MB, 在所有 Java 提交中击败了18.49%的用户
     */
public ListNode mergeKLists(ListNode[] lists) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (true) {
        int minIndex = -1;
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] == null) {
                continue;
            }
            if (minIndex == -1) {
                minIndex = i;
            }else{
                //比较链表的结点，取到最小的结点
                if (lists[i].val <= lists[minIndex].val) {
                    minIndex = i;
                }
            }
        }
        //若是找到最小的结点位置
        if (minIndex != -1) {
            cur.next = lists[minIndex];
            cur = cur.next;
            lists[minIndex] = lists[minIndex].next;
        }
        //若是当前没有最小的结点位置了
        if (minIndex == -1) {
            return dummy.next;
        }
    }
}

方式二：堆排序法（对于最小值比较可使用优先队列来实现）

思路：一开始将多个数组的第一个元素全部扔到堆中(优先队列)，接着以堆当前的数量为条件不断的添加进入以及取出最小值连接到新链表上。

相较于方式一：省去了多次重复的比较，因为在方式一中每次一轮比较都是n个链表的数量元素，中间会有多次重复比较，而在这里时间效率直接提升，每次都是放在一个升序的队列里。

/**
 * 方式二：堆排序法
 * 思路：使用优先队列，首先将所有链表的首元素添加到队列中，接着以队列的元素数量作为条件来进行不断的添加与取出最小的值连接到最新的链表，最终就可以得到一个升序的链表。
 * 
 * 执行用时：4 ms, 在所有 Java 提交中击败了63.11%的用户
 * 内存消耗：43 MB, 在所有 Java 提交中击败了80.38%的用户
 */
public ListNode mergeKLists(ListNode[] lists) {
    //优先队列（可看做是堆）
    PriorityQueue<ListNode> heap = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
    //将当前队列扔到堆中排序
    for (ListNode list : lists) {
        if (list != null) {
            heap.offer(list);
        }
    }
    //定义虚拟头结点
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    //以堆中heap的数量作为条件
    while (heap.size() > 0) {
        ListNode node = heap.poll();//最小的元素
        cur.next = node;
        cur = cur.next;
        //向堆中添加新的元素
        if (node.next != null) {
            heap.offer(node.next);
        }
    }
    return dummy.next;
}

其他：

方法：①遍历所有链表存到数组中。②对数组进行快速排序。③对排序后的数组进行生成链表返回。

时间复杂度：O(n+logn.n+n)=>O(logn)
空间复杂度：O(n+n)=>O(n)，排序与创建都用到O(n)

2.6.24

前言

基本概念

剑指offer

剑指 Offer 06. 从尾到头打印链表【简单】

剑指 Offer 18. 删除链表的节点【简单】

牛客

简单

判断表中是否有环【简单】

链表中倒数最后k个结点【简单】

两个链表的第一个公共结点【简单】

判断一个链表是否为回文结构【简单】

删除有序链表中重复的元素-I【简单】

中等

链表内指定区间反转【中等】

删除链表的倒数第 n 个结点（【中等】，牛客/第3题的升级版）

链表中的两数相加【中等】

单链表的排序【中等，三种方案包含哨兵、归并排序，只有归并排序在leetcode不超时】

链表中环的入口结点【中等】

删除有序链表中重复的元素-II【中等】

leetcode

简单

反转链表【简单】

合并两个排序列表【简单】

回文链表【简单】

141. 环形链表【简单】

142. 环形链表 II【中等】

移除链表元素【简单】

中等

160. 相交链表【中等】

2. 两数相加【中等】

奇偶链表【中等】

707. 设计链表【中等】

24. 两两交换链表中的节点【中等】

困难

K 个一组翻转链表【困难】

合并K个排序链表【困难】

评论区请在客户端页面查看