创建一个基础工具类来放ListNode及定义其一些常用方法
160.相交链表、找出两个链表的交点✅
206. 反转链表
- 解法一：头插法
- 解法二：递归
21. 合并两个有序链表
- 解法一：暴力破解
- 解法二：递归
83. 删除排序链表中的重复元素
- 解法一：暴力
- 解法二：递归
19. 删除链表的倒数第 N 个结点
24. 两两交换链表中的节点
445. 两数相加 II
234. 回文链表
725. 分隔链表
328. 奇偶链表
- 解法一：
- 解法二：分离节点后合并

创建一个基础工具类来放ListNode及定义其一些常用方法

package com.shiers.leetcode;
/**
 * Demo class
 *
 * @author shierS
 * @date 2021/4/25
 */
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode() {
    }
    public ListNode(int val) {
        this.val = val;
    }
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
    //初始化一个List
    public static ListNode initList(int[] arr){
        if (arr.length < 1){
            return null;
        }
        ListNode head = new ListNode(arr[0]);
        ListNode my = head;
        for (int i = 1; i < arr.length; i++) {
            ListNode thisListNode = new ListNode(arr[i]);
            my.next = thisListNode;
            my = thisListNode;
        }
        return head;
    }
    //输出一个List
    public static void printlist(ListNode head){
        while (head != null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}

160.相交链表、找出两个链表的交点✅

编写一个程序，找到两个单链表相交的起始节点。要求时间复杂度为 O(N)，空间复杂度为 O(1)。如果不存在交点则返回 null。
✅链表 - 图1
思路：
设 A 的长度为 a + c，B 的长度为 b + c，其中 c 为尾部公共部分长度，可知 a + c + b = b + c + a。
当访问 A 链表的指针访问到链表尾部时，令它从链表 B 的头部开始访问链表 B；同样地，当访问 B 链表的指针访问到链表尾部时，令它从链表 A 的头部开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。
如果不存在交点，那么 a + b = b + a，以下实现代码中 l1 和 l2 会同时为 null，从而退出循环。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode lnA = headA,lnB = headB;
        while(lnA != lnB){
            lnA=(lnA==null?headB:lnA.next);
            lnB=(lnB==null?headA:lnB.next);
        }
        return lnA;
    }
}

扩展：
如果只是判断是否存在交点，那么就是另一个问题。有两种解法：

把第一个链表的结尾连接到第二个链表的开头，看第二个链表是否存在环；
或者直接比较两个链表的最后一个节点是否相同。
206. 反转链表
给你单链表的头节点head，请你反转链表，并返回反转后的链表。

解法一：头插法
思路：
head指针，指向原列表的头节点，后续用于操作的节点指针
创建一个新的节点newHead，开始指向null，该节点始终用来指向新链表的头节点
创建一个next指针，用来备份head指针在原链表中的下一个节点
步骤1、创建next指针备份head的下一个节点
步骤2、操纵head节点指向newHead节点的next（也就是指向新链表的头节点）

步骤3、使得newHead指向head节点
步骤4、head节点指向next指向的节点

重复操作即可

public static class ListNode {
    int val;
    ListNode next;
    ListNode() {
    }
    ListNode(int val) {
        this.val = val;
    }
    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
public static ListNode reverseList(ListNode head) {
    ListNode newHead = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = newHead.next;
        newHead.next = head;
        head = next;
    }
    return newHead.next;
}

解法二：递归

思路：

使用递归要注意，reverseList（next）递归完成之后，就默认其中部分完成了所有操作，即已经反转了，只需要将当前位置的头节点反转完成即可（即递归完之后的代码步骤）
千万不要试着取理解每一次递归的具体操作，很容易将自己绕晕😂😂😂（过来人经验：走火入魔很痛苦），知道这个以后发现递归真的超好用，顿悟了！

public static ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) { //递归出口
        return head;
    }
    ListNode next = head.next;
    ListNode newHead = reverseList(next); //next之后经过递归已经完成反向
    next.next = head;
    head.next = null;
    return newHead; 返回头节点
}

21. 合并两个有序链表

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

解法一：暴力破解

时间复杂度 O(M+N)
空间复杂度 O(1)
空间换时间，多了一个哑节点的空间，一次遍历通过

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode head = new ListNode(-1);//哑节点
    ListNode prev = head;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            prev.next = l1;
            l1 = l1.next;
        } else {
            prev.next = l2;
            l2 = l2.next;
        }
        prev = prev.next;
    }
    // 任一为空，直接连接另一条链表
    if (l1 == null) {
        prev.next = l2;
    }
    if (l2 == null) {
        prev.next = l1;
    }
    return head;
}

解法二：递归

时间复杂度 O(M+N)
空间复杂度 O(M+N) 最坏情况下需要叠加栈

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

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

存在一个按升序排列的链表，给你这个链表的头节点head，请你删除所有重复的元素，使每个元素只出现一次。
返回同样按升序排列的结果链表。
✅链表 - 图9

解法一：暴力

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode temp = head;//temp指针始终指向已经删除重复元素节点链表的尾节点
        ListNode next = head.next;//该指针循环遍历原来链表
        while(next != null){
            if(temp.val != next.val){
                temp.next = next; 
                temp = temp.next;
            }
            next = next.next;
        }
        temp.next = null;//最后给尾节滞空，防止链表最后有多个相同元素
        return head;
    }
}

解法二：递归

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        head.next = deleteDuplicates(head.next);
        return head.val == head.next.val?head.next:head; 
    }
}

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

给你一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
✅链表 - 图10
思路：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null || head.next == null){
            return null;
        }
        ListNode dummyHead = new ListNode(-1); //设置哨兵防止删除数组第一个元素！！！
        dummyHead.next = head;
        ListNode prev = dummyHead;
        ListNode tail = dummyHead;
        int flag = 0;
        while(tail != null){
            if(flag > n){  //保持俩个指针距离位n+1
                prev = prev.next;
            }
            tail = tail.next;
            flag++;
        };
        ListNode temp = prev.next;
        prev.next = prev.next.next;
        temp.next = null;//删除节点滞空！
        return dummyHead.next;//记得跳过哨兵
    }
}

优化：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while( n-- > 0 ){
            fast = fast.next;
        }
        if(fast == null) return head.next;
        ListNode slow = head;
        while( fast.next != null ){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

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

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
✅链表 - 图12
思路：

public static ListNode swapPairs(ListNode head) {
    ListNode node = new ListNode(-1); //设置哨兵节点
    node.next = head;
    ListNode first = node;
    while (first.next != null && first.next.next != null) {
        ListNode second = first.next;
        ListNode third = first.next.next;
        //交换
        first.next = third;
        second.next = third.next;
        third.next = second;
        //移动first指针
        first = second;
    }
    return node.next;
}

445. 两数相加 II

给你两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶：
如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例：
输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出： 7 -> 8 -> 0 -> 7
解释： 7243 + 564 = 7807

利用栈结构实现

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode node = new ListNode(-1);
    ListNode index = node;
    Stack s0 = new Stack<Integer>();
    Stack s1 = new Stack<Integer>();
    Stack s2 = new Stack<Integer>();
    //放入元素
    while (l1 != null) {
        s1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 != null) {
        s2.push(l2.val);
        l2 = l2.next;
    }
    int num = 0;//进位存储
    //取出元素并相加
    while (!s1.empty() && !s2.empty()) {
        int temp = num + (int) s1.pop() + (int) s2.pop();
        num = temp / 10;//获取进位值
        temp = temp % 10;//获取个位数
        s0.push(temp);
    }
    //将剩余链表种的值取出
    while (!s1.empty()){
        int temp = num + (int) s1.pop();
        num = temp / 10;//获取进位值
        temp = temp % 10;//获取个位数
        s0.push(temp);
    }
    while (!s2.empty()){
        int temp = num + (int) s2.pop();
        num = temp / 10;//获取进位值
        temp = temp % 10;//获取个位数
        s0.push(temp);
    }
    //判断是否还有进位
    if(num != 0){
        s0.push(num);
    }
    //生成新链表
    while (!s0.empty()){
        index.next = new ListNode((int)s0.pop());
        index = index.next;
    }
    return node.next;
}

优化

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    Stack<Integer> l1Stack = buildStack(l1);
    Stack<Integer> l2Stack = buildStack(l2);
    ListNode head = new ListNode(-1);
    int carry = 0;
    while (!l1Stack.isEmpty() || !l2Stack.isEmpty() || carry != 0) {
        int x = l1Stack.isEmpty() ? 0 : l1Stack.pop();
        int y = l2Stack.isEmpty() ? 0 : l2Stack.pop();
        int sum = x + y + carry;
        ListNode node = new ListNode(sum % 10);
        node.next = head.next;
        head.next = node;
        carry = sum / 10;
    }
    return head.next;
}
private Stack<Integer> buildStack(ListNode l) {
    Stack<Integer> stack = new Stack<>();
    while (l != null) {
        stack.push(l.val);
        l = l.next;
    }
    return stack;
}

234. 回文链表

请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

进阶以后难度为中等

解法一：数组列表

思路：
将链表存入数组列表中，利用双向指针比较元素是否相等

复杂度分析
时间复杂度：O(n)，其中 n 指的是链表的元素个数。
第一步：遍历链表并将值复制到数组中，O(n)。
第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。
总的时间复杂度：O(2n) = O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。

注意： get()方法对127以内的整形数值会直接封装成值返回，但是对大于127的值会返回对象，因此你的比较是进行对象地址的比较，实际上是不对的。你得用equals()方法比较。 1、首先Integer是对象，比较两个对象是否相等不能使用==，应该使用equals 2、让我们查看jdk源码，在使用==比较Integer类型时，默认会缓存 -128至127（包括-128和127），如果超过这个范围，则会new，所以两个对象的地址不一样，==则会返回false。 3、如果非要使用==，-128至127（包括-128和127）范围内可以使用==比较，返回true，反之false。

public static boolean isPalindrome(ListNode head) {
    //结束条件,链表只有一个或为空也是回文
    if(head == null || head.next == null) return true;
    List<Integer> list = new ArrayList<Integer>();
    // 将链表的值复制到数组中
    while(head != null){
        list.add(head.val);
        head = head.next;
    }
    // 使用双指针判断是否回文
    int before = 0;
    int back = list.size()-1;
    while(before < back){
        if(!list.get(before).equals(list.get(back))){
            return false;
        }
        before++;
        back--;
    }
    return true;
}

解法二：利用栈

// 利用栈，和数组链表一样
public static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    Stack<Integer> stack = new Stack<>();
    ListNode node = head;
    // 把链表存入栈中
    while (node != null) {
        stack.push(node.val);
        node = node.next;
    }
    //在来一次和栈中元素比较
    node = head;
    while (node != null) {
        if (node.val != stack.pop()) {
            return false;
        }
        node = node.next;
    }
    return true;
}

解法三：递归

该解法超出时间限制😂

//递归
public static boolean isPalindrome(ListNode head) {
    //结束条件,链表只有一个或为空也是回文
    if(head == null || head.next == null) return true;
    ListNode tail = head.next;
    ListNode temp = head;
    while (tail.next != null){
        temp = tail;
        tail = tail.next;
    }
    //while循环完毕后 tail指向最后一个元素
    //判断首尾元素是否相等
    if(head.val != tail.val) return false;
    //删除首尾相同元素的节点
    head = head.next;
    //删除尾部
    temp.next = null;
    //递归调用，判断去掉首尾元素的剩余链表
    return isPalindrome(head);
}

方法四：进阶最优——反转链表

未命名绘图.png

// 最优：反转链表
public static boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    // 1、利用快慢指针找到中间节点
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev = null; //指向slow的之前一个
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }
    // 2、切断链表
    if (fast == null) { // 偶数情况
        prev.next = null; // 切断
    } else { // 奇数情况
        slow = slow.next; // 跳过中间节点
        prev.next = null;// 切断
    }
    // 3、反转链表
    ListNode newslow = reverseList(slow); 
    // 4、比较
    while (head != null) {
        if (head.val != newslow.val) {
            return false;
        }
        head = head.next;
        newslow = newslow.next;
    }
    return true;
}
//206.反转链表
public static ListNode reverseList(ListNode head) {
    ListNode node = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = node.next;
        node.next = head;
        head = next;
    }
    return node.next;
}

725. 分隔链表

给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1，也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出，并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例： 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]

示例 1： 输入: root = [1, 2, 3], k = 5 输出: [[1],[2],[3],[],[]] 解释: 输入输出各部分都应该是链表，而不是数组。例如, 输入的结点 root 的 val= 1, root.next.val = 2, oot.next.next.val = 3, 且 root.next.next.next = null。第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2： 输入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] 解释: 输入被分成了几个连续的部分，并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。

public static ListNode[] splitListToParts(ListNode root, int k) {
    int length = 0;
    ListNode node = root;
    // 获取链表元素个数
    while (node != null) {
        length++;
        node = node.next;
    }
    ListNode[] arrListNode = new ListNode[k];
    //计算分隔链表位置
    int mod = length % k; // 取余计算出前几个子链表长度需要+1
    int size = length / k; // 子链表平均长度
    node = root;
    for (int i = 0; node != null && i < k ; i++) {
        ListNode son = node;
        arrListNode[i] = son; // 对数组赋值子链表头部
        int curSize = size + (mod-- > 0 ? 1 : 0); // 子链表长度
        for (int j = 0; j < curSize-1; j++) { //走到子链表尾部
            node = node.next;
        }
        //切断链表
        ListNode next = node.next;
        node.next = null;
        node = next;
    }
    return arrListNode;
}

328. 奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例 1: 输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL

示例 2: 输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL

说明: 应当保持奇数节点和偶数节点的相对顺序。链表的第一个节点视为奇数节点，第二个节点视为偶数节点，以此类推。

解法一：

一开始写出来的，和方法二一样，比较笨和繁琐

public static ListNode oddEvenList1(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode node = head.next.next; //设置遍历节点指针
    ListNode j = head; //奇数链表尾指针
    ListNode o = head.next; //偶数链表尾指针
    while (node != null && node.next != null) {
        ListNode next = node.next;
        // 将偶数链表链接到node下一个节点
        o.next = next;
        o = next;
        // 将node节点插入到奇数链表尾部
        node.next = j.next;
        j.next = node;
        j = node;
        node = next.next;//node移动俩位到下一个 奇数 节点上
    }
    //如果链表长度为奇数，需要处理最后一个奇数节点
    if (node != null) {
        ListNode next = node.next;
        o.next = next;
        node.next = j.next;
        j.next = node;
    }
    return head;
}

解法二：分离节点后合并

public static ListNode oddEvenList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode jtail = head;//奇链表尾节点
    ListNode ohead = head.next; //偶列表头节点
    ListNode otail = ohead; //偶列表尾节点
    while (otail != null && otail.next != null){
        jtail.next = otail.next;
        jtail = jtail.next;
        otail.next = otail.next.next;
        otail = otail.next;
    }
    //链接奇偶链表
    jtail.next = ohead;
    return head;
}

✅链表

创建一个基础工具类来放ListNode及定义其一些常用方法

160.相交链表、找出两个链表的交点✅

206. 反转链表

解法一：头插法

解法二：递归

21. 合并两个有序链表

解法一：暴力破解

解法二：递归

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

解法一：暴力

解法二：递归

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

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

445. 两数相加 II

234. 回文链表

解法一：数组列表

解法二：利用栈

解法三：递归

方法四：进阶最优——反转链表

725. 分隔链表

328. 奇偶链表

解法一：

解法二：分离节点后合并