• LeetCode 热题 HOT 100：链表专题

    LeetCode 热题 HOT 100：https://leetcode.cn/problem-list/2cktkvj/

    文章目录

    2. 两数相加

    题目链接：https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    实现步骤：

    • 将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如：987 + 23 = 987 + 023 = 1010。
    • 每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值。
    • 如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点。
    class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode p1 = l1, p2 = l2, q = pre;
        int sign = 0;
        while(p1 != null || p2 != null){
            int sum = 0;
            if(p1 == null){
                sum = p2.val + sign;
                p2 = p2.next;
            }else if(p2 == null){
                sum = p1.val + sign;
                p1 = p1.next;
            }else{
                sum = p1.val + p2.val + sign;
                p1 = p1.next;
                p2 = p2.next;
            }
            sign = sum >= 10 ? 1 : 0; // 修改标志位
            ListNode node = new ListNode(sum % 10);
            q.next = node;
            q = q.next;
        }
        if(sign == 1){
            ListNode node = new ListNode(1);
            q.next = node;
        }
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

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

    题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0); // 伪头部节点
        pre.next = head;
        ListNode p, q;
        p = q = pre;
        int co = 0;
        while(q.next != null){ // 先让q指针先走n步，然后p指针再继续走
            if(++co > n){
                p = p.next;
            }
            q = q.next;
        }// 结束循环时，p指针指向倒数第N+1位
        p.next = p.next.next;
        // 注意避坑点：return head; 是存在问题的：当链表中只有一个元素时，p指针会进行删除后，head 还是指向原来的那个结点。
        return pre.next; 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    21. 合并两个有序链表

    题目链接：https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                p.next = list1;
                list1 = list1.next;
            }else{
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        p.next = list1 == null ? list2 : list1;
        return res.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    23. 合并 K 个升序链表

    题目链接：https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = null;
        for(int i = 0; i < lists.length; i ++){
            head = mergeTwoLists(head, lists[i]);
        }
        return head;
    }

    public ListNode mergeTwoLists(ListNode a, ListNode b){
        ListNode res = new ListNode(0);
        ListNode p = res;
        while(a!=null && b!=null){
            if(a.val < b.val){
                p.next = a;
                a = a.next;
            }else{
                p.next = b;
                b = b.next;
            }
            p = p.next;
        }
        p.next = a != null ? a : b;
        return res.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    141. 环形链表

    题目链接：https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked

    哈希表做法（时间复杂度较高）：

    public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        Set<ListNode> set = new HashSet(); // set 记录结点的地址
        while(head.next != null){
            if(set.contains(head)){
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    快慢指针做法1：

    public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null){
            return false;
        }
        ListNode slow, fast;
        slow = head;
        fast = head.next;
        // slow 每次向前走一步，fast 每次向前走两步（可以任意多步）
        // 当存在环时，fast 由于走得快，会发生扣圈的情况，且最终与 slow 相遇
        // 当不存在环时，fast 可能在某次循环后，发生当前位置为空，或下一位置为空的两种情况，当然由于走的快，最终会返回false。
        // 总之，循环的结束条件，要么出现环 slow == fast，要么 fast 先一步为空！ 
        while(slow != fast && fast != null && fast.next != null){
            // 注意：fast != null 要先于fast.next != null 来判断，以防止控制帧异常
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow == fast;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    快慢指针做法2（思路同下方“环形链表2”）：

    public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;

        while(true){
            if(fast==null || fast.next==null){
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
            if(slow==fast){
                return true;
            }
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    142. 环形链表 II

    题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked

    哈希表做法（时间复杂度较高）：

    public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode p = head;
        while(p!=null){
            if(set.contains(p)){
                return p;
            }
            set.add(p);
            p = p.next;
        }
        return null;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    快慢指针，实现思路如下：

    • 设 fast 每次走两个节点， slow 每次走一个节点。环外有 a 个结点，环内有 b 个结点。
    • 相遇时，fast 走了 f 步，slow 走了 s 步。
      ① f = 2s
      ② f = s + nb 表示 f 比 s 多走了 n*b 步，即 n 圈。这样表示的原因在于扣圈。
      化简得：f = 2nb, s = nb
    • 设刚开始 slow 指针从开始到环的入口要走 k 步：k = a + nb （n = 0,1,2,…）
    • 由于 s = n*b，即已经走了 n*b 步了，那么此时只需要再走 a 步即可回到链表入环的起点。
    public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                break;
            }
        }
        fast = head; // fast回到链表起点，与 slow 一同遍历 a 步
        while(slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    148. 排序链表

    题目链接：https://leetcode.cn/problems/sort-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    使用优先队列模仿堆：

    class Solution {
    public ListNode sortList(ListNode head) {
        PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> b.val-a.val); // 大顶堆
        while(head != null){
            queue.offer(head); // 从堆底插入
            head = head.next;
        }
        ListNode pre = new ListNode(0);
        while(!queue.isEmpty()){
            ListNode p = queue.poll(); // 出队列并调整堆
            p.next = pre.next; // 头插法倒序
            pre.next = p;
        }
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    自顶向下归并排序1： 时间复杂度 O(nlogn)，空间复杂度O(logn)

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

    // 归并排序
    // 将头指针和尾指针之前的元素进行排序，初始尾指针为null，即最后一个节点的下一个空节点
    public ListNode mergeSort(ListNode head, ListNode tail){
        if(head == tail){
            return head;
        }
        if(head.next == tail){ // 隔离出来单独结点
            head.next = null;
            return head;
        }
        ListNode slow, fast;
        slow = fast = head;
        while(fast != tail){
            slow = slow.next;
            fast = fast.next;
            if(fast != tail){
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode l1 = mergeSort(head, mid); // 将 head 至 mid 之前的节点进行排序
        ListNode l2 = mergeSort(mid, tail); // 将 mid 至 tail 之前的节点进行排序
        return mergeList(l1, l2);
    }

    // 合并两个有序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48

    参考链接：https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/?envType=featured-list&envId=2cktkvj%3FenvType%3Dfeatured-list&envId=2cktkvj

    自顶向下归并排序2：

    class Solution {
    public ListNode sortList(ListNode head) {
        return mergeSort(head);
    }
    
	// 归并排序
    public ListNode mergeSort(ListNode head){
        if(head==null || head.next==null){
            return head;
        }
        ListNode slow = head; // 快慢指针
        ListNode fast = head.next;

        while(fast!=null && fast.next!=null){ // 查询中间节点
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next; // 断链
        slow.next = null;

        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(mid);
        return mergeList(l1, l2);
    }

	// 合并两个有序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44

    自底向上排序： 时间复杂度 O(nlog)，空间复杂度O(n)

    class Solution {
    public ListNode sortList(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;

        int len = getLength(head); // 获取长度
        for(int step = 1; step < len; step *=2){ //依次将链表分块的长度分为：1，2，4...
            ListNode curr = pre.next;
            ListNode p = pre;
            // p 用于链接每次分块的链表，如：第一次循环链接分块长度为1的链表，然后链接分块长度为2的链表
            while(curr != null){
                ListNode h1 = curr; // 第一块链表的头
                ListNode h2 = spilt(h1, step); // 第二块链表的头
                curr = spilt(h2, step); // 下次while循环的头，也是给到h1
                // 合并第一二块链表，下次while循环合并第三四块链表....
                ListNode res = mergeList(h1, h2);
                // 将合并后的链表链接起来，并将指针移到链表的最后一个节点，以链接下次的链表
                p.next = res;
                while(p.next!=null){
                    p = p.next;
                }
            }
        }
        return pre.next;
    }

    // 分割链表，并返回后半段的链头
    public ListNode spilt(ListNode head, int step){
        if(head == null){
            return null;
        }
        ListNode p = head;
        for(int i = 1; i < step && p.next!=null; i ++){
            p = p.next;
        }
        ListNode right = p.next;
        p.next = null; // 切断连接
        return right;
    }

    // 求链表长度
    public int getLength(ListNode head){
        int co = 0;
        while(head!=null){
            co++;
            head = head.next;
        }
        return co;
    }

    // 合并两个升序链表
    public ListNode mergeList(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode p = pre;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else{
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null ? l2:l1;
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68

    160. 相交链表

    题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    实现步骤：

    • 设不是公共部分的节点数分别是 a、b，公共节点数为 n。
    • 如果有公共节点，则当 p1 遍历完 a+n 个节点时，再在另一个链表的头部遍历 b 个节点时，必相交。原因在于此时 p2 遍历了 b+n+a 个结点。
    • 如果没有公共节点部分，那么 p1 与 p2 经历了上文的步骤后，都会为 null， null==null 为 true。
      因此跳出循环，要么 null == null，要么都不为空找到了公共节点。
    public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA;
        ListNode p2 = headB;
        while(p1 != p2){
            p1 = p1 == null ? headB : p1.next;
            p2 = p2 == null ? headA : p2.next;
        }
        return p1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    206. 反转链表

    题目链接：https://leetcode.cn/problems/reverse-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = new ListNode(0);
        ListNode p = head;
        while(p!=null){
            ListNode q = p.next;
            p.next = pre.next;
            pre.next = p;
            p = q;
        }
        return pre.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    234. 回文链表

    题目链接：https://leetcode.cn/problems/palindrome-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj

    class Solution {
    public boolean isPalindrome(ListNode head) {
        Deque<ListNode> stack = new LinkedList<>();
        ListNode p = head;
        while(p!=null){
            stack.push(p);
            p = p.next;
        }
        while(head != null){
            p = stack.pop();
            if(p.val != head.val){
                return false;
            }
            head = head.next;
        }
        return true;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    R语言 一种功能强大的数据分析、统计建模 可视化 免费、开源且跨平台 的编程语言
    《小狗钱钱》阅读笔记（三）
    数字IC前端学习笔记：数字乘法器的优化设计（基2布斯乘法器）
    Android抓包工具——Fiddler
    gitlab跨版本升级
    关于fifo和ram时序验证
    vue 调试工具devtools
    Air Quality Index，简称AQI
    基于Android的乐鲜生活APP设计与实现
    汽车RNC主动降噪算法DSP C程序实现
  • 原文地址：https://blog.csdn.net/weixin_43819566/article/details/132783854