LeetCode 热题 HOT 100：链表专题

怼烎@ 2023-10-15 19:49 51阅读 0赞

LeetCode 热题 HOT 100：[https://leetcode.cn/problem-list/2cktkvj/][https_leetcode.cn_problem-list_2cktkvj]

--------------------

#### 文章目录 ####

*   *  2. 两数相加
     *  19. 删除链表的倒数第 N 个结点
     *  21. 合并两个有序链表
     *  23. 合并 K 个升序链表
     *  141. 环形链表
     *  142. 环形链表 II
     *  148. 排序链表
     *  160. 相交链表
     *  206. 反转链表
     *  234. 回文链表

--------------------

### 2. 两数相加 ###

题目链接：[https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

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

题目链接：[https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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; 
        }
    }

--------------------

### 21. 合并两个有序链表 ###

题目链接：[https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

### 23. 合并 K 个升序链表 ###

题目链接：[https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

### 141. 环形链表 ###

题目链接：[https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked][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：**

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;
        }
    }

**快慢指针做法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;
                }
            }
        }
    }

--------------------

### 142. 环形链表 II ###

题目链接：[https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked][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;
        }
    }

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

*  设 **`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;
        }
    }

--------------------

### 148. 排序链表 ###

题目链接：[https://leetcode.cn/problems/sort-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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：** 时间复杂度 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;
        }
    }

参考链接：[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][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;
        }
    }

**自底向上排序：** 时间复杂度 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;
        }
    }

--------------------

### 160. 相交链表 ###

题目链接：[https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

### 206. 反转链表 ###

题目链接：[https://leetcode.cn/problems/reverse-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

### 234. 回文链表 ###

题目链接：[https://leetcode.cn/problems/palindrome-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj][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;
        }
    }

--------------------

[https_leetcode.cn_problem-list_2cktkvj]: https://leetcode.cn/problem-list/2cktkvj/
[https_leetcode.cn_problems_add-two-numbers_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/add-two-numbers/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_remove-nth-node-from-end-of-list_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/remove-nth-node-from-end-of-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_merge-two-sorted-lists_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/merge-two-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_merge-k-sorted-lists_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/merge-k-sorted-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_linked-list-cycle_description_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-100-liked
[https_leetcode.cn_problems_linked-list-cycle-ii_envType_study-plan-v2_envId_top-100-liked]: https://leetcode.cn/problems/linked-list-cycle-ii/?envType=study-plan-v2&envId=top-100-liked
[https_leetcode.cn_problems_sort-list_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/sort-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[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]: https://leetcode.cn/problems/sort-list/solutions/492301/pai-xu-lian-biao-by-leetcode-solution/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_intersection-of-two-linked-lists_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/intersection-of-two-linked-lists/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_reverse-linked-list_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/reverse-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj
[https_leetcode.cn_problems_palindrome-linked-list_envType_featured-list_envId_2cktkvj_envType_featured-list_envId_2cktkvj]: https://leetcode.cn/problems/palindrome-linked-list/?envType=featured-list&envId=2cktkvj?envType=featured-list&envId=2cktkvj