难度说明：🟢简单🟡中等🔴困难

hot100-07-链表

🟢01-相交链表（160）

1.题目内容

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

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

2.题解思路

👻方法1：判断交点

规律分析：无论A、B是否有相交节点，最终都会指向同一个相同的节点（要么是公共尾部、要么是NULL）

定义两个指针，然后指针分别遍历链表，判断指针是否相遇。例如指针A先遍历链表A，当A遍历完了就指向链表B继续遍历；指针B先遍历链表B，当链表B遍历完了就指向链表A继续遍历，当两个指针相遇的时候循环结束，此时这个指针指向的就是公共节点的位置（这个公共节点要么存在，要么为NULL），最终返回指针位置，对应的就是相交链表的公共尾部

• 初始化：让pointA和pointB分别指向链表A、B的头节点，之后两个指针分别以步幅为1的速度向链表的尾部遍历
• 当pointA遍历到链表A的尾节点（走了a个节点），然后将pointA指向链表B的头部，继续向后遍历，直到走到c1（即公共尾部），此时指针共走了a+(b-c)步
• 当pointB遍历到链表B的尾节点（走了b个节点），然后将pointB指向链表A的头部，继续向后遍历，直到走到c1（即公共尾部），此时指针共走了b+(a-c)步

从数学逻辑上分析，a+(b-c)=b+(a-c)是需要成立的：也就是说两个指针同时遍历两个链表，必然会相遇，这个相遇的点就是所谓概念上的公共节点（node为null表示链表无相交，node不为null说明存在公共节点）

• 如果c>0（说明存在公共尾部），即表示c1这个节点是存在的，两链表同时到达c1
• 如果c=0（说明两链表没有公共尾部），即pointA和pointB都指向NULL

/**
 * 160-相交链表
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode common = null;
        // 判断边界（链表为NULL的情况）
        if (headA == null || headB == null) {
            return null;
        }

        // 初始化指针(pointA、pointB分别指向A、B链表头节点)
        ListNode pointA = headA;
        ListNode pointB = headB;

        // 两个指针指向同一个节点，遍历结束（根据这个共同节点判断是否为null进而确定是否存在公共节点）
        while (pointA != pointB) {
            // 遍历A链表
            if (pointA != null) {
                // 如果pointA不为NULL则不断向后移动
                pointA = pointA.next;
            } else {
                // 如果pointA为NULL则跳到B链表
                pointA = headB;
            }

            // 遍历B链表
            if (pointB != null) {
                // 如果pointB不为NULL则不断向后移动
                pointB = pointB.next;
            } else {
                // 如果pointB为NULL则跳到A链表
                pointB = headA;
            }
        }

        // pointA、pointB最终都指向同一个节点,要么是公共节点、要么是NULL,所以此处返回任意一个都可以
        return pointA;
    }

}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

🟢02-反转链表（206）

1.题目内容

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

例如：[1,2,3,4,5] =》[5,4,3,2,1]

2.题解思路

👻方法1：直接颠倒（头插）

​ 思路分析：和数组反转的思路类似，可以直接将值颠倒。数组可以从尾部开始进行遍历，而链表则需从头节点进行遍历。因此此处有一个很巧妙的设定，可以利用头插的思路去实现。定义一个新的链表用于存储结果，依次循环遍历链表元素，将元素取出并插入到链表的最前面（也就是让当前元素的next指针指向当前的res即可，这点可以通过ListNode的构造函数实现）

​ 核心：循环遍历链表元素，将元素以"头插"的形式插入链表

/**
 * 206.反转链表
 * 思路：直接颠倒（头插）
 */
public class Solution1 {
    public ListNode reverseList(ListNode head) {

        // 定义结果
        ListNode res = null;

        // 遍历链表
        for(ListNode cur = head; cur != null; cur = cur.next) {
            // 传入指定值和链表，创建一个ListNode进行初始化，其next指向指定链表（可以理解为头插法的一种体现）
            res = new ListNode(cur.val,res);
        }

        // 返回结果
        return res;
    }
    
    // 参考
    public ListNode reverse(ListNode head) {
        // 定义虚拟链表头
        ListNode dummy = null; // 此处其作为尾节点

        // 定义指针用于遍历head
        ListNode cur = head;
        while(cur!=null){
            dummy = new ListNode(cur.val,dummy); // 头插
            cur = cur.next; // 指针后移
        }

        // 返回结果
        return dummy;
    }
}


/**
 * 链表节点定义
 */
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

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

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

复杂度分析

• 时间复杂度：
• 空间复杂度：

👻方法2：栈（先进后出）

​ 思路分析：链表为【1->2->3->4->5->∅】，需反转为【5->4->3->2->1->∅】，可通过借助栈来实现

​ 核心：循环迭代链表元素，依次入栈，然后依次出栈存入新链表

/**
 * 206.反转链表
 * 思路：栈
 */
public class Solution2 {
    public ListNode reverseList(ListNode head) {

        // 定义结果
        ListNode res = new ListNode(0);
        // 定义当前节点指针
        ListNode cur = res;

        // 定义栈存放中间结果
        Stack<ListNode> stack = new Stack<ListNode>();

        // 遍历链表元素，入栈
        while (head != null) {
            stack.push(head);
            head = head.next;
        }

        // 依次出栈构建新链表
        while(!stack.isEmpty()) {
            cur.next = stack.pop();
            cur = cur.next; // 更新节点
        }
        cur.next = null; // 需设置尾节点为null，否则提示（Error - Found cycle in the ListNode）
        return res.next; // 排除第一个初始化的节点（初始化起始值为0，需从其下一个节点遍历）
    }
}

👻方法3：迭代法

​ 思路分析：链表为【1->2->3->4->5->∅】，需反转为【5->4->3->2->1->∅】，可通过迭代的方式进行

• 反转的思路是将当前节点的next指针指向其前一个节点
  • 初始化prev、curr（当前节点，理解为节点指针）
  • 迭代元素：记录当前节点的下一个节点，将当前节点的next指针指向prev，然后prev、curr向后移动（即先将当前的curr作为下一个节点的prev，然后curr继续指向下一个节点）

/**
 * 206.反转链表
 * 思路：迭代
 */
public class Solution3 {
    public ListNode reverseList(ListNode head) {

        // 记录当前节点和当前节点的上一个节点
        ListNode prev = null;
        ListNode curr = head;

        // 迭代链表
        while (curr != null) {
            ListNode next = curr.next; // 记录当前节点的下一个节点
            curr.next = prev; // 将当前节点的next指向指向prev
            prev = curr; // prev设定为当前节点（会作为下一节点的prev）
            curr = next; // curr指向下一个节点（继续遍历）
        }

        // 返回链表
        return prev;
    }
}

3.复盘

🟢03-回文链表（234）

1.题目内容

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

​ 回文链表：指的是以链表中间为中心点，两边对称。例如[1 2 2 1]

​ 对于回文的判断可以有多个方向切入：

• 思路1：基于回文概念，可以理解为类似字符串abccba，它正着读和反着读是一样的，因此可以考虑构建一个集合存储它的反转序列，然后对比两个集合对应位置的数值是否匹配（即正转和反转的序列是否一致）
• 思路2：分割+反转概念，回文序列的前半部分和后半部分是相互对称的，可以先找到中点位置分为前后部分，然后将后半部分进行反转，再与前半部分进行对比确认是否一致

2.题解思路

👻方法1：栈（先进后出）

​ 定义栈存储元素，然后遍历链表和依次出栈的元素进行比较。优化上体现的是，不需要遍历整个集合，可以只遍历一半的元素即可。即在第一次遍历的时候记录链表长度，然后第二次遍历的时候只遍历一半的元素即可

/**
 * 234.回文链表
 * 思路：栈
 */
public class Solution1 {

    public boolean isPalindrome(ListNode head) {

        // 指定stack存储类型
        Stack<Integer> stack = new Stack<>();

        // 记录链表节点指针
        ListNode cur = head;

        // 依次入栈
        while (cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }

        // 遍历链表，和出栈元素依次进行比较，如果出现不一致则认为非回文
        while (head != null) {
            if (head.val != stack.pop()) {
                return false;
            }
            // 继续指向下一个
            head = head.next;
        }

        // 返回
        return true;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.isPalindrome(head));
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

// 链表逆序打印
private void printListNode(ListNode head) {
    if (head == null)
        return;
    printListNode(head.next);
    System.out.println(head.val);
}

👻方法2：回文判断（头插思路）

​ 分析：用正常的回文判断思路，正序和逆序的顺序一致，那么方法1中用到栈，此处则用反转链表概念实现（参考反转链表的实现，遍历元素构建链表的时候可以采用头插法进行构建，构建的对应就是反转链表），随后同时遍历两个链表，判断序列是否一致即可

/**
 * 回文链表
 */
public class Solution2 {

    /**
     * 回文：因为链表长度不定，没办法类似数组这样去用双指针两头走进行判断
     * 因此此处就是正常的思路：正序遍历顺序=逆序遍历顺序 则满足回文
     * 正序：就是正常遍历链表
     * 逆序：类似链表反转的思路（可以用栈，或者头插法生成链表）
     */
    public boolean isPalindrome(ListNode head) {

        // 定义链表指针
        ListNode cur = head;

        // 遍历链表，利用头插法生成链表
        ListNode newNode = null; // 初始化节点为null（因为头插，则这个初始化的newNode最后会被放到尾巴处）
        while(cur!=null){
            newNode = new ListNode(cur.val,newNode); // 头插法构建新链表
            cur = cur.next; // 指针后移
        }

        // 再次正序遍历链表元素，然后依次和出栈元素进行比较
        while(head!=null){// 此处没有用新指针，而是直接用head作为指针了
            if(head.val != newNode.val){
                return false;
            }
            // 两个指针链表继续后移
            head = head.next;
            newNode = newNode.next;
        }
        return true;
    }

}

👻方法...：

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

🟢04-环形链表（141）

1.题目内容

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

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

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

2.题解思路

👻方法1：哈希表

​ 核心：判断链表是否有环，类似遍历链表节点的next，判断这个next是否已经被遍历过，转化为哈希表概念就是对已遍历的元素进行标记，如果next指向的节点是已经被遍历了的则说明存在环

​ 核心：循环遍历链表，然后记录下已访问的元素，如果元素的next节点在已遍历的元素中

​ 注意：此处HashSet集合元素类型应为ListNode，因为链表节点内的val值是可以相同的，此处要关注的是链表的节点指向，如果仅仅存值则容易误判

/**
 * 141-环形链表
 * 思路：哈希表  迭代、标记，校验next是否已被标记
 */
public class Solution {

    public boolean hasCycle(ListNode head) {

        // 定义HashSet存储元素
        HashSet<ListNode> set = new HashSet<ListNode>();

        // 遍历链表，校验next是否已存在标记
        while(head != null) {
            if(set.contains(head)) {
                return true;
            }
            // 将当前节点进行标记
            set.add(head);
            // 迭代下一个元素
            head = head.next;
        }
        return false;

    }

}

复杂度分析

• 时间复杂度：
• 空间复杂度：

👻方法1：快慢指针

​ 定义快慢指针（fast、slow），只要存在环，则这两个指针必定会在某一时刻相遇

public class Solution2 {

    /**
     * 定义快慢指针进行环形判断：
     * 1.如果链表不存在环，则必然会遍历到链表尾部（也就是说快指针到达链表尾部的时候，就会跳出链表遍历了）
     * 2.如果链表存在环，则快慢指针必然会相遇（因为存在环，快慢指针必然会在圈子内转圈圈，最终在某个时刻相遇）
     */
    public boolean hasCycle(ListNode head) {
        // 定义快慢指针（两者的起点相同）
        ListNode slow = head;
        ListNode fast = head;

        // 迭代链表，看指针是否会相遇
        while (fast != null && fast.next != null) {
            // 此处必须先走后判断（否则起始值一样的情况下slow==fast始终成立）
            slow = slow.next; // 指针继续后移
            fast = fast.next.next; // 指针继续后移
            if (slow == fast) {
                return true; // 快慢指针相遇，则说明存在环
            }
        }
        // 跳出循环，说明快指针遍历到链表尾部了，即不存在环
        return false;
    }
    
}

​ 需注意此处快慢指针的概念是："起点相同，快指针步长更长，慢指针步长更短"（即龟兔赛跑，两个起点是一样的，但是乌龟慢，兔子快，如果都绕着树转总会相遇），因此此处设定可以是起点相同，快指针走两步，慢指针走一步，然后进行判断

​ 此处容易陷入误区：就是以为快指针就是起点在前面、慢指针就是起点在后面，遍历过程中两个步长又设置为一样，这样的快慢设计是永远不可能相遇的（没有速度差，慢指针永远追不上，这个思路是个坑需要注意）

🟡05-环形链表II（142）

1.题目内容

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

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

不允许修改 链表。

2.题解思路

👻方法1：哈希表

​ 和141-环形链表题型类似，遍历元素将其加入哈希表，如果遍历过程中发现元素已存在则说明存在环，则直接返回这个节点

/**
 * 142-环形链表II
 * 思路：哈希表  迭代、标记，校验next是否已被标记
 */
public class Solution1 {

    public ListNode detectCycle(ListNode head) {

        // 定义HashSet存储元素
        HashSet<ListNode> set = new HashSet<ListNode>();

        // 遍历链表，校验next是否已存在标记
        while(head != null) {
            if(set.contains(head)) {
                return head;
            }
            // 将当前节点进行标记
            set.add(head);
            // 迭代下一个元素
            head = head.next;
        }
        return null;

    }

}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

🟢06-合并两个有序链表（21）

1.题目内容

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

2.题解思路

👻方法1：迭代法

​ 定义一个新链表，然后不断比较两个链表的节点大小，将其依次纳入链表中：

• 校验边界值：link1、link2为null的情况
• 当link1、link2都不为null，依次遍历链表，校验对应头节点的值，将较小的节点加入新链表，以此类推
• 当跳出循环（上述操作遍历到某个链表尾部时就会跳出循环），因此需要将剩余的节点进行追加

/**
 * 21-合并链表
 */
public class Solution1 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // 定义虚拟节点头
        ListNode res = new ListNode(0); // 这个链表头节点可以为任意，因为不需要用到这个头节点的值

        // 定义对应链表指针
        ListNode cur = res;

        // 边界值确认（l1、l2为空的情况）
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        // l1、l2都不为空的情况,遍历链表（不断比较l1、l2各个节点的值）
        while (l1 != null && l2 != null) {
            // 如果l1当前节点的值小于l2当前节点
            if (l1.val <= l2.val) {
                cur.next = l1;// 让指针指向当前这个较小的节点链表
                l1 = l1.next; // l1 指向下一个节点（l1向后移动）
            } else {
                cur.next = l2;// 让指针指向当前这个较小的节点链表
                l2 = l2.next; // l2 指向下一个节点（l2向后移动）
            }
            // 指针向后移动
            cur = cur.next;
        }

        // 如果l1、l2还有没有覆盖到的节点（因为不知道l1、l2哪个长，所以上述操作循环结束，可能长的链表中还有节点没有覆盖到）
        if (l1 != null) {
            cur.next = l1; // 将当前l1剩下的节点全部进行追加
        }
        if (l2 != null) {
            cur.next = l2; // 将当前l2剩下的节点全部进行追加
        }
        // 最后返回虚拟节点头的next指针
        return res.next;
    }

}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

/**
 * 021 合并两个有序链表
 */
public class Solution {

    /**
     * 合并两个有序链表，本质上就是依次比较两个链表元素大小，然后进行插入操作
     * 两个链表本身有序，因此构建一个链表存储结果，依次插入满足条件的数据即可
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {

        // 定义链表头
        ListNode dummy = new ListNode(0);
        // 定义新链表的指针
        ListNode cur =dummy;

        // 定义两个链表的遍历指针
        ListNode pointer1 = list1;
        ListNode pointer2 = list2;

        /**
         * 依次遍历链表元素，比较链表元素
         * （由于未知链表长度，因此在同时遍历的时候如果有一个链表遍历到了尾节点就停止遍历，将next指针指向另一个遍历完的链表位置即可）
         */
        while(pointer1 != null && pointer2 != null) {
            // 如果当前链表1的元素小于链表2的元素，则指针指向链表1元素
            if(pointer1.val < pointer2.val) {
                // 将链表1元素加入新链表
                ListNode temp = new ListNode(pointer1.val);
                cur.next = temp;
                // 链表1指针和新链表指针后移
                pointer1 = pointer1.next;
                cur = cur.next;
            }else{
                ListNode temp = new ListNode(pointer2.val);
                cur.next = temp;
                // 链表2指针和新链表指针后移
                pointer2 = pointer2.next;
                cur = cur.next;
            }
        }

        // 跳出循环说明至少其中一个链表遍历到尾部，此时判断哪个为空说明该链表遍历完成，只需要将新链表的next指向剩下的即可
        if(pointer1 != null) {
            cur.next = pointer1;
        }
        if(pointer2 != null) {
            cur.next = pointer2;
        }

        // 返回新链表
        return dummy.next;

    }

}

🟡07-两数相加（2）

1.题目内容

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

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

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

PS：需注意此处并不是要将每个链表对应位置数字相加，实际上应该要将链表组成的数字进行相加，然后再放在一个新链表中，链表中每个节点存一个数字

例如[2,4,3] [5,6,4]应该为342+465=807需要将807逆序放入链表

2.题解思路

❌方法1：硬核拆解（超出内存限制）

​ 回归题意，最硬核的解法就是分别得到每个链表表示的数字，然后进行相加得到sum，最后将这个sum转化为链表的各个节点。

​ 这个方案虽然硬核，但是非常暴力，使用上会超出内存限制。很明显需要结合题目特性进行优化

/**
 * 2-两数相加
 * 思路：将链表组成的数字相加，然后再放在一个新链表中，链表中每个节点存一个数字）
 */
public class Solution2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // 定义链表
        ListNode res = new ListNode(0);
        // 定义链表指针
        ListNode cur = res;

        // 分别遍历链表，组合数字
        StringBuffer sb1 = new StringBuffer();
        while(l1!=null){
            sb1.append(l1.val);
        }
        StringBuffer sb2 = new StringBuffer();
        while(l2!=null){
            sb2.append(l2.val);
        }
        // 计算数字之和
        int sum = Integer.valueOf(sb1.toString()) + Integer.valueOf(sb2.toString());

        // 将数字加入链表
        String sumStr = String.valueOf(sum);
        for(int i=0;i<sumStr.length();i++){
            cur.val += sumStr.charAt(i);
            cur = cur.next;
        }
        // 返回链表
        return res.next;
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

👻方法2：节点相加、处理进位

​ 因为数字本身是按照逆序排序的，所以正常按照各个节点相加，然后处理进位关系即可

​ 例如[2,4,3] [5,6,4]，处理为2+5、4+6=10（存0进1）、3+4+1=8（进位），然后将708逆序存入链表，得到807

​ 那么这题的思路就是通过循环遍历得到对应节点之和，然后处理好进位关系即可

​

​ 这点遍历上有点小技巧：

• 循环条件：因为两个链表可能不等长，因此遍历过程中需要进行NPE处理，如果某个链表为null则其后续所有节点置为0即可。只有当两个链表都遍历完成，才认为遍历结束
• 最后的进位：由于最后一个节点也可能存在进位，因此最后如果存在进位还需额外补上（或者将进位条件也加入循环，处理好对应的情况即可）

/**
 * 2-两数相加
 * 思路：将各个节点的值进行相加，处理相应的进位关系
 */
public class Solution3 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // 定义链表
        ListNode res = new ListNode(0);

        // 定义链表指针
        ListNode cur = res;

        // 边界值处理（l1为null，或者l2为null）
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        // 定义进位标识
        boolean carry = false;
        // 循环遍历两个链表
        while (l1 != null || l2 != null || carry) {
            // 可能会有个链表先为空，需做空指针处理
            int a = l1 == null ? 0 : l1.val;
            int b = l2 == null ? 0 : l2.val;

            // 获取对应节点值之和，需要处理进位关系
            int currentVal = carry ? (a + b + 1) : (a + b); // 如果carry为true需要加上进位
            // 处理当前节点存储数据和进位配置(如果currentVal>=10表示需要进位，当前节点直接存储取模后的数字)
            cur.next = new ListNode(currentVal % 10);
            carry = currentVal >= 10 ? true : false;

            // 指针后移
            cur = cur.next;

            // 判断是否有下一个节点
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // 处理最后的进位(也可加进位条件加入循环，而不需此处额外处理)
        /*
        if (carry) {
            cur.next = new ListNode(1);
        }
         */

        // 返回链表结果
        return res.next;
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

public class Solution {

    /**
     * 两个数字之和：数字存放时基于链表逆序存放的
     * 参考243+564=》708（进位补到后面的位置）
     * 也就是说正序遍历两个链表相应的元素，如果存在进位则添加进位，保留个位数作为元素存储
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        // 定义虚拟链表头
        ListNode dummy = new ListNode(0);

        // 定义新链表指针
        ListNode cur = dummy;

        // 依次遍历两个链表元素，将对应位置数据元素进行相加(由于未知链表长度，所以对于比较短的链表此处可以通过补0来优化实现)
        ListNode pointer1 = l1, pointer2 = l2;
        boolean carry = false;

        // 由于链表长度未定，则此处设定是两个链表都遍历完成才退出循环，对于不足长度的链表则进行补0操作
        while (pointer1 != null || pointer2 != null) {
            int val1 = pointer1 == null ? 0 : pointer1.val; // 处理NPE
            int val2 = pointer2 == null ? 0 : pointer2.val; // 处理NPE
            int sum = val1 + val2 + (carry?1:0);
            // 获取个位数值
            int val = sum % 10; // 获取个位数值
            // 判断是否存在进位
            carry = (sum / 10 != 0) ; // 除数不为0说明带进位
            // 存储元素
            cur.next = new ListNode(val);

            // 操作完成指针均后移
            cur = cur.next;

            // 处理NPE
            if(pointer1 != null) pointer1 = pointer1.next;
            if(pointer2 != null) pointer2 = pointer2.next;
        }

        // 处理最后的进位
        if (carry) {
            cur.next = new ListNode(1);
        }

        // 返回链表
        return dummy.next;

    }

}

🟡08-删除链表倒数的第N个节点（19）

1.题目内容

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

2.题解思路

​ 核心：删除节点的核心在于先找到要删除的那个节点进行删除操作，而不需要全部重复搬一遍，链表的删除操作实际就是将delNode的前一个节点的next指向下一个其下下个节点（因为单链表并没有前指针，因此此处要操作的并不是待删除节点，而是将待删除节点的前一个节点的next指针进行修改）

​ 删除倒数第n个节点，有两种思路，从遍历的角度来看，就是正向遍历链表，然后删除第L-n+1位置的节点

• 正向思路（两次遍历链表）：第1次遍历得到链表长度L，第2次遍历第L-n+1的位置做删除操作
• 逆向思路（链表+栈）：利用栈的先进后出特性，第1次遍历入栈，第2次遍历出栈（第n个位置做"删除操作"）

​ 核心：需要注意的是，不需要设定为将节点加入新链表，主要是定位到那个要删除的节点的前一个节点 prev，然后设置prev.next=prev.next.next

👻方法1：链表遍历

• 两次链表遍历：（注意遍历的时候用的指针，如果用同一个指针则需要进行重置，否则会干扰）
  • 第1次遍历：计算链表长度
  • 第2次遍历：让指针移动到指定的位置，然后删除对应位置的元素（即让当前指针的next指向next.next）

/**
 * 2-删除倒数第N个节点（链表）
 * 思路1：两次链表遍历，第1次获取链表长度，第2次在对应L-n+1做删除操作（即让当前节点的next指向下下个节点）
 */
public class Solution1 {

    public ListNode removeNthFromEnd(ListNode head, int n) {

        // 定义链表(初始化为原链表)
        ListNode res = new ListNode(0, head);

        // 定义链表指针
        ListNode cur = res;

        // 1.获取链表长度（注意不要用同一个指针）
        int len = 0;
        while (head != null) {
            len++;
            head = head.next;
        }

        // 2.遍历链表,删除第L-N+1个节点(去掉链表初始节点)
        for (int i = 1; i < len - n + 1; i++) {
            cur = cur.next; // 指针移动
        }
        // 当前指针移动向下下个节点（表示删除下个节点）
        cur.next = cur.next.next;
        return res.next;
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

👻方法2：栈

• 利用栈的先进后出特性
  • 第1次遍历：依次进栈
  • 第2次遍历：依次出栈，排除指定计数N的值

public ListNode removeNthFromEnd(ListNode head, int n) {

        // 定义链表(初始化为head原链表)
        ListNode dummy = new ListNode(0,head);
        // 定义链表指针
        ListNode cur = dummy;

        // 定义栈
        Stack<ListNode> stack = new Stack<ListNode>();

        // 1.依次入栈
        while (head != null) {
            stack.push(head);
            head = head.next; // 指针后移
        }

        // 2.依次出栈，当第n个位置则剔除
        for(int i = 0; i < n; i++) {
            stack.pop();
        }
        // 获取到倒数第n-1的节点，更新其next值即可
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return dummy.next;
    }

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

🟡09-两两交换链表中的节点（24）

1.题目内容

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

2.题解思路

👻方法1：遍历法

​ 参考上述分析图示，基于此进行逻辑设计即可，此处需注意步骤执行的先后顺序，以及指针移动（指针移动不是cur=cur.next 因为在这个交换过程中cur.next已经变了，所以指针遍历的下一个元素应该是一开始记录的node1）

public ListNode swapPairs(ListNode head) {
    // 增设虚拟头节点
    ListNode dummy = new ListNode(0, head);
    // 设置节点指针
    ListNode cur = dummy;

    // 遍历链表，进行元素交换(结合图示分析，链表节点交换操作需要两个元素)
    while (cur.next != null && cur.next.next != null) {
        // 记录节点信息
        ListNode node3 = cur.next.next.next;
        ListNode node1 = cur.next;
        ListNode node2 = cur.next.next;
        // 执行节点交换
        cur.next = node2;   // 步骤1
        node2.next = node1; // 步骤2 
        node1.next = node3; // 步骤3
        // 指针后移，准备下一轮交换(需注意此处cur指向的要遍历的下一个节点应为node1,而非cur.next)
        cur = node1;
    }
    // 返回链表
    return dummy.next;
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

👻方法2：递归法

​ 递归思路：先翻转前面的节点，再将翻转后的节点next指针指向节点后续链表。

​ 需要注意的是，本题的递归终点是遇到链表尾或者剩余链表中只有一个节点，这时候无法进行翻转，需要返回null或者单个节点。

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 边界条件
        if(head == null || head.next == null){
            return head;
        }
        // 记录下个节点
        ListNode newNode = head.next;
        // 翻转节点
        head.next = swapPairs(newNode.next);
        newNode.next = head;
        return newNode;
    }
}

// 参考
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head==null||head.next==null) return head;
        ListNode two = head.next;
        head.next = two.next;
        two.next = head;
        head.next = swapPairs(head.next);
        return two;
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

🟡10-随机链表的复制（138）

1.题目内容

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

你的代码 只 接受原链表的头节点 head 作为传入参数。

2.题解思路

参考题解

​ 思路分析：这道题的含义指的是有这么一个链表节点，它包含两个指针，一个指针指向next（下一个节点），另一个指针则是指向random（指向链表中的任意节点或空节点）。如果只是普通链表的复制，那么只需要循环遍历链表直接创建新的节点（其后一个节点可以通过next进行定位）

​ 但是题目中节点的设定还有一个random指针，由于random的特殊性（可以指向链表中任意节点或空节点），因此无法在一次遍历过程中就确定下来（因为如果是指向后面的节点，可能节点还没有创建出来，进而无法确定）。因此此处的题目思路可以拆分为两个步骤：步骤①先创建链表中的所有节点、步骤②根据指针关系构建节点连接

• 步骤①：创建链表节点（暂未设定next、random指针）
  • 此处有一个设计巧思，通过定义一个HashMap将旧节点和新节点进行映射，通过这个集合就可以根据某个旧节点信息快速定位到对应的新节点
• 步骤②：构建节点关系（依次遍历原链表，根据原指针信息确定新链表的指针关系），此处需要关注三个要素
  • 如何拿到cur对应的新节点？ =》通过map.get(cur)获取
  • newNode的next是什么？ =》通过map.get(cur.next)获取（理论上分析新节点的下一个节点应该对应为原节点的下一个节点在map的映射）
  • newNode的random是什么？ =》通过map.get(cur.random)获取（理论上分析新节点的random节点应该对应为原节点的random节点在map的映射）

👻方法1：哈希表

​ 基于上述题解，按照步骤进行设计

public Node copyRandomList(Node head) {

    // 构建新链表
    Node res = new Node(0);

    // 定义链表指针
    Node cur = head;

    // 构建一个哈希表结构存储当前节点和对应Random节点的对应关系
    Map<Node, Node> map = new HashMap<Node, Node>();

    // 步骤①：遍历链表，用于对应创建节点（无next、random）
    // 定义哈希表
    while (cur != null) {
        Node newNode = new Node(cur.val); // 创建新节点
        map.put(cur, newNode); // 构建当前节点和新节点的映射（用于后续构建节点关系）
        cur = cur.next; // 指针后移
    }

    // 步骤②：构建链表节点之间的联系（设置next、random）
    cur = head; // 重新初始化链表指针
    while (cur != null) {
        // 根据key获取到对应的新链表节点
        Node newNode = map.get(cur);

        // 寻找这个新链表节点的next和random值

        // 设置next指针（新节点对应的next指针即为cur.next在map中的映射值）
        newNode.next = map.get(cur.next);
        // 设置random指针（新节点对应的random指针即为cur.random在map中的映射值）
        newNode.random = map.get(cur.random);

        // 指针后移
        cur = cur.next;
    }

    // 返回结果
    return map.get(head);
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘

​ 问题分析：由于random的存在，所以无法像是遍历单链表那样获取到next节点然后直接进行构建，因为在遍历的过程中指向的random节点无法明确有没有被创建，因此也就很难构建节点之间的指针联系。既然指针关系一开始很难确定，那么就采用提前占位、延后装配的思想，先把对应的节点创建出来，然后再填充它的指针关系

​ 因此此处通过引入Map将老节点和对应的新节点进行映射，第一次遍历是创建新链表的所有节点（只初始化val，而不关联指针关系），第二次遍历则是根据老链表的指针关系去填充新链表的节点间的指针关系（可以通过Map去一一匹配：key就是老节点，value就是其在新链表中对应的新节点，而老节点的next、custom节点在新链表中对应的新节点就是其相应节点所在的value）

​ 此处还有一点小技巧需注意的是，无需额外构建所谓的虚拟节点去构建链表，只需要通过返回map.get(head)就能达到新链表的头节点了，不需要在遍历过程中又拼接一遍（不要陷入惯性思维，要具体分析）

public class Solution {
    /**
     * 随机指针的深拷贝
     * 由于随机指针的存在，无法直接通过一次遍历链表就获取到next、random的值
     * 思路：采用提前占位、延后装配的概念，先把链表的节点给初始化出来，然后再一步步去完善指针关系
     * 因此将问题转化为如何去构建指针关系，此处采用Map哈希表将原节点和对应的新节点分别作为key、value进行存储
     * 遍历这个Map的同时可以拿到对应的新节点并进行匹配，设置指针关系
     */
    public Node copyRandomList(Node head) {

        // 定义Map<OldNode,NewNode>存储老节点和新节点的映射关系，通过这个map就能获取对应的联系
        Map<Node,Node> map = new HashMap<Node,Node>();
        // 1.循环遍历链表，将老节点和对应其在新链表的新节点关联起来
        Node cur = head;
        while(cur!=null){
            // 创建新节点，此处只是预创节点，还没有建立指针关联
            Node newNode = new Node(cur.val);
            // 构建节点关联
            map.put(cur,newNode);
            // 构建完成，指针后移
            cur = cur.next;
        }

        // 2.上述新链表的节点都预创完成，则此处进一步构建节点的指针联系（通过遍历Map进行构建）
        Set<Node> oldNodeSet = map.keySet();
        Iterator<Node> oldNodeItr = oldNodeSet.iterator();
        while(oldNodeItr.hasNext()){
            // 获取老节点在新链表中对应的新节点，填充其next、random
            Node oldNode = oldNodeItr.next();
            Node newNode = map.get(oldNode); // 老节点对应的新节点就是key对应的value
            newNode.next = map.get(oldNode.next); // 类似地，设定新节点的next，其next就是指向原老节点指向的next作为key对应的value
            newNode.random = map.get(oldNode.random); // 以此类推
        }

        // 返回响应结果
        return map.get(head);
    }
}

🟡11-排序链表（148）

参考题解：可结合其他排序算法思路进行理解：常见排序算法、链表排序参考

1.题目内容

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

2.题解思路

👻方法1：暴力法

​ 最硬核的方式就是先遍历一遍节点，然后存入集合中，通过工具类进行排序，然后根据排序结果构建新链表

/**
 * 148-单链表排序
 * 思路1：暴力法（遍历链表节点、排序、根据排序结果回写）
 */
public class Solution1 {

    public ListNode sortList(ListNode head) {
        // 定义结果
        ListNode res = new ListNode(0);

        // 定义指针
        ListNode cur = head;

        // 定义集合存储
        ArrayList<Integer> list = new ArrayList<Integer>();

        // 步骤①：遍历链表
        while (cur != null) {
            list.add(cur.val);
            cur = cur.next; // 指针后移
        }

        // 排序
        Collections.sort(list); // 借助工具类进行排序

        // 初始化新链表指针
        cur = res;
        // 步骤②：回写链表
        for (int i : list) {
            cur.next = new ListNode(i);
            cur = cur.next;// 指针后移
        }
        // 返回结果
        return res.next;
    }

}

复杂度分析

• 时间复杂度：
• 空间复杂度：

补充：如何找链表的中点（快慢指针原理）

​ 快慢指针的原理类似于时钟里的分针时针，在链表中，二者同时从head首节点出发，快指针一次走两步，慢指针一次走一步，当快指针走到终点时，慢指针所在位置即为链表的中点

// 奇数是返回中点，偶数时返回第2个
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

// 奇数是返回中点，偶数时返回第1个（因为fast起点快了1步）
class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

​ 也有其他方式实现，例如丢到集合里面去进行计数

// 计数法
public ListNode finMid3(ListNode head) {
    // 定义遍历指针
    ListNode cur = head;

    // 定义集合存储元素并在遍历过程中计数
    List<ListNode> list = new ArrayList<ListNode>();
    while (cur != null) {
        list.add(cur);
        cur = cur.next;
    }

    return list.get(list.size()/2 - 1); // list.size()/2 默认返回的是第2个，
}

👻方法2：自顶向下的归并排序

class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    // 递归
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        // 找到链表中点，然后分别对左右两边进行排序，返回合并后的排序规则
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    // 合并两个有序的列表
    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

3.复盘

• 解题核心：
  • 寻找链表中点，然后将链表劈成两半分别对两边进行递归排序，并对排序后的结果进行合并
  • 此处需注意链表中点的获取和在迭代过程中的使用（调试的过程发现递归死循环了，因为一开始获取中点的方法拿到的中点始终是第2个，所以导致错误，改成第1个思路正确）

public class Solution3 {

    /**
     * 自顶向下的归并排序：
     * 思路：将链表对半分，然后分别对左右两边进行排序，对排序完成的结果进行合并
     */
    public ListNode sortList(ListNode head) {

        // 递归出口
        if (head == null || head.next == null ) {
            return head;
        }

        // 寻找链表的中点（此处中点需为第1个，否则迭代过程中出错）
        ListNode finMid = finMid(head);

        // 右边链表
        ListNode right = sortList(finMid.next); // 右边链表的头节点就是中间节点的下一个节点

        // 左边链表
        finMid.next = null;
        ListNode left = sortList(head); // 左边链表的头节点就是head，但需要将中间节点断开才是前一半（所以此处需要先获取右边的，然后再拿左边）

        // 返回合并后的链表
        return mergeList(left, right);
    }

    // 查找链表中间节点
    public ListNode finMid(ListNode head) {
        // 此处中间节点获取有个点需要注意，即fast起点其实是先走1步（体现的效果就是偶数的时候选择的是两个中的第1个）
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 合并两个有序链表
    public static ListNode mergeList(ListNode l1, ListNode l2) {
        // 合并两个有序的链表：依次判断链表元素
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;

        // 定义两个链表的遍历指针
        ListNode pointer1 = l1;
        ListNode pointer2 = l2;

        // 遍历链表（当两个链表其中一个链表遍历到尾部，则可结束循环，然后将剩余的元素直接补到尾部即可）
        while (pointer1 != null && pointer2 != null) {
            // 如果pointer1指向元素小于等于pointer2指向元素，则加入链表
            if (pointer1.val <= pointer2.val) {
                cur.next = new ListNode(pointer1.val);
                // 指针后移
                pointer1 = pointer1.next;
                cur = cur.next;
            } else {
                // 加入pointer2指向元素
                cur.next = new ListNode(pointer2.val);
                // 指针后移
                pointer2 = pointer2.next;
                cur = cur.next;
            }
        }
        // 接入尾巴
        if (pointer1 != null) {
            cur.next = pointer1;
        }
        if (pointer2 != null) {
            cur.next = pointer2;
        }
        // 返回结果
        return dummy.next;
    }
}

🟡12-LRU缓存（146）

1.题目内容

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

2.题解思路

参考题解：LRU缓存算法思路

思路分析

​ 首先理解什么是LRU：Least Recently Used 最近最少使用，即当缓存域满了之后会通过这种算法优先淘汰最近最少使用的元素。

思路1：通过访问频次大小进行淘汰

可能一般构建的思路就是类似数组存储，然后记录每个元素的访问频次：

• 数据插入：判断是否超出阈值，如果超出阈值则淘汰访问频次最低的元素（进行替换），如果没有超出阈值则正常追加数据
• 数据访问：更新记录访问频次

​

思路2：不设定访问频次，而是类似排队的概念，让活跃的数据排在淘汰后排

​ 基于上述流程分析，优化LRU的设计思路，如何通过不记录访问频次的方式实现LRU？即类似排队的概念，选定一个方向进行淘汰，当数据被访问时就将其重新排到后面去，以此达到不记录访问频次就能实现LRU淘汰的效果 =》淘汰尾部的数据（尾部存储的是最久远访问的数据）、让活跃的节点移动到队列另一段

• 淘汰谁？：采用头插法，确保最新插入的数据在头部，依次类推，当依次插入数据超出缓存阈值的时候，此时尾部的数据会被淘汰（就是最先插入的数据会被淘汰）
• 如何更新访问频次？：此处没有访问频次的概念，而是将活跃的数据移动到另一端

​ 继续剖析题目，如果get、put的时间复杂度需为O(1)，不免联想到哈希表。其次要支持在任意位置灵活地快速插入和删除元素，可借助链表。因此会联想到可以通过哈希表+链表的结构实现LRU缓存，因此初步设计数据结构为：

​ 此处基于上述设计可以思考几个问题：

• 为什么要使用双向链表而不是单向链表？
  • 链表的删除操作需要涉及到prev节点的next指针修改，而单向链表并没有存储前驱节点的指针，因此引入双向链表进行优化
• 哈希表中已经存储了key，为什么链表还要存储key和value？
  • 动态删除链表节点的时候需要相应删除对应哈希表的值，因此在删除链表节点的时候可以根据存储的key到哈希表中删除节点（即根据key定位链表节点进行删除）
• 虚拟头节点和虚拟尾节点有什么用？
  • 在链表场景中虚拟节点被广泛应用，又称为哨兵节点，通常不保存任何数据（使用虚拟节点可以统一处理链表中所有节点的插入和删除操作，而不需要考虑头、尾节点的特殊情况）

​

👻方法1：基于LinkedHashMap实现

​ 基于上述分析引入数据结构：哈希表+双向链表（JAVA中可以采用LinkedHashMap的实现），如果是算法的考察一般是要手撕双向链表的设计，而不让直接用LinkedHashMap。此处先基于LinkedHashMap理解LRU算法的实现思路

/**
 * 146-LRU缓存
 * 基于LinkedHashMap实现:存储key、value
 */
class LRUCache {

    // 定义缓存容量阈值
    int capacity ;

    // 定义数据结构（存储集合）
    LinkedHashMap <Integer, Integer> cache;

    // 构造函数
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>();
    }

    // 访问元素（判断元素是否存在，更新访问节点位置（重新插入：即先删后插））
    public int get(int key) {
        // 如果指定值存在
        if(cache.containsKey(key)) {
            // 记录当前值
            int value = cache.get(key);
            // 移除节点
            cache.remove(key);
            // 重新插入节点到链表尾部
            cache.put(key, value);
            return value;
        }else{
            return -1;
        }
    }

    // 插入元素（判断插入数据是否存在，存储则直接覆盖，如果不存在则继续判断是否超出阈值，超出阈值则需要触发LRU淘汰机制）
    public void put(int key, int value) {
        if(cache.containsKey(key)) {
            // key已存在则覆盖（先删后加）
            cache.remove(key);
            cache.put(key, value);
        }else{
            // 校验阈值
            if(cache.size()>=capacity){
                // 超出阈值触发清理(因为LinkedHashMap是有序的，所以此处通过迭代器获取到第一个元素，然后直接移除)
                Iterator<Integer> iterator = cache.keySet().iterator();
                cache.remove(iterator.next());
            }
            // 最终将新的数据节点插入
            cache.put(key, value);
        }
    }
}

复杂度分析

• 时间复杂度：
• 空间复杂度：

3.复盘