LeetCode刷题第五周

布满荆棘的人生 2023-02-28 11:13 49阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70]

> 最近看到好朋友们一个又一个的都开始入职了，心里有种说不出来的滋味。即替他们开心，又对自己两年后找工作时候的不确定充满期待和惶恐。许多朋友们今年陆续都开始找工作了。讲实话，压力挺大的，现在的大学都教的那tm是个啥东西，一个sql讲半年，一个Java语法讲半年。老早就不想上了，从大一寒假确定目标要去沪漂做后端到现在一直都在自学，培训班里六个月要学完的东西，我花了快一年半的时间自学，现在才学到分布式。做技术这条路，任重道远…害，戒骄戒躁继续前行吧。心里其实说着急吧，却又着急不起来，因为距离去找工作还有很多时间，足够复习和准备面试了。但也不能懈怠，往后得多和身边的巨佬们交流交流，编程路上我还是个弟弟。总之，马上大三了，再往前走走，我得跑起来。  
> — 2020年7月21日 by Hudie

### 文章目录 ###

*  链表专题
 *   *  简单
     *   *  21. 合并两个有序链表
         *  83. 删除排序链表中的重复元素
     *  中等
     *   *  2. 两数相加
         *  19. 删除链表的倒数第N个节点
         *  24. 两两交换链表中的节点
         *  61. 旋转链表
         *  82. 删除排序链表中的重复元素 II
         *  86. 分隔链表
     *  困难
     *   *  23. 合并K个排序链表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 1]

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

# 链表专题 #

## 简单 ##

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

**题目链接：** [点击跳转至本题][Link 1]

**题目大意：  
将两个升序链表合并为一个新的升序链表并返回。(新链表是通过拼接给定的两个链表的所有节点组成的。)**

**解题思路：`哨兵节点`\+`迭代`**  
设置哨兵节点prehead，方便返回合并后的节点，在遍历中维护prev指针，不断使其next域指向l1和l2中较小的值，遍历结束时将l1或l2中剩余的值添加到prev的next域中。返回哨兵节点prehead的next域。  
**时间复杂度：**`O(n+m)`

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */
    class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            //创建哨兵节点
            ListNode prehead = new ListNode(-1);
            ListNode prev = prehead;
            while(l1 != null  && l2 != null){ 
                if(l1.val <= l2.val){ 
                    prev.next = l1;
                    l1 = l1.next;
                }else if(l1.val > l2.val){ 
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }
            prev.next = l2==null ? l1:l2;
            return prehead.next;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 2]

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

**题目链接：** [点击跳转至本题][Link 2]

**题目大意：  
给定一个排序链表，要求删除所有重复的元素，使得每个元素只出现一次。**  
![在这里插入图片描述][2020072416044483.png]

**解题思路：`直接法`**  
由于head是头指针不能动的缘故，设置工作指针p代替head指针移动。遍历过程中，当p当前节点的val和下一个节点的val相等，就将p节点链接上后一个节点的后一个节点，即实现了删除重复元素。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode deleteDuplicates(ListNode head) { 
            //p作为工作指针
            ListNode p = head;
            while(p!= null && p.next != null){ 
                if(p.val == p.next.val){ 
                    //发现后面有和此处相同的val就连接到其下一个
                    p.next = p.next.next;
                }else{ 
                    p = p.next;
                }
            }
            return head;
        }
    }

## 中等 ##

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

**题目链接：** [点击跳转至本题][Link 3]

**题目大意：  
给定两个非空的链表用来表示两个非负的整数，各自的位数按照逆序存储在链表中(每个节点只能存储一位数字)。要求你将这两个整数加起来，返回一个新的链表来表示它们的和。(说明：除了数字0之外，这两个整数都不会以0开头。)  
示例：**  
![在这里插入图片描述][20200721023625281.png]

**解题思路：`模拟加法进位`**  
创建一个节点l3作为第三个链表的头节点，分别使用p、q、v三个指针指向这三个链表。当链表l1和l2都不为空时向后遍历，从个位开始相加，变量carry记录是否有进位(加法只会进1位或不进位)，并将对应位的和对10取模，作为值加入新链表l3中。待遍历结束，对carry 进行判断，若仍有进位则对l3的下一个节点补1。  
另外：本题需注意链表l3并不是从头节点开始存储，而是l3.next，所以最后的结果返回的是l3.next。

**时间复杂度**：`O(max(m,n))`

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
            //创建l3链表的头节点
            ListNode l3 = new ListNode(0);
            //创建指针p,q,v分别指向链表l1,l2,l3
            ListNode p = l1,q = l2,v = l3;
            //初始化进位变量
            int carry = 0;
            while(p != null || q != null){ 
                int x = (p != null) ? p.val:0;
                int y = (q != null) ? q.val:0;
                int sum = x + y + carry;
                carry = sum/10;
                //注意:这里是从链表l3的第二个节点开始存储
                v.next = new ListNode(sum%10);
                v = v.next;
                if(p != null) p = p.next;
                if(q != null) q = q.next;
            }
            //遍历结束时,若进位仍>0则追加一个值为1的新节点
            if(carry > 0){ 
                v.next = new ListNode(1);
            }
            return l3.next;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 3]

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

**题目链接：** [点击跳转至本题][Link 4]

**题目大意：  
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。(说明：给定的 n 保证是有效的。)**

**解题思路：`哨兵节点`\+`迭代`**  
创建哨兵节点prehead，prehead.next指向待求链表的头节点head。由于head作为头节点不方便移动，故设置指针p指向代替head工作，第一次遍历求出链表长度length，第二次遍历做删除工作。

**时间复杂度：**`O(Length)`

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        //删除倒数第N个节点==删除下标为(length-N)的节点
        public ListNode removeNthFromEnd(ListNode head, int n) { 
            //创建哨兵节点
            ListNode prehead = new ListNode(0);
            prehead.next = head;
            int length = 0;
            ListNode p = head;
            while(p != null){ 
                length++;
                p = p.next;
            }
            length -= n;
            //使指针p指向哨兵节点
            p = prehead;
            //将p移动到要删除位置的前一个位置
            while(length > 0){ 
                length--;
                p = p.next;
            }
            p.next = p.next.next;
            return prehead.next;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 4]

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

**题目链接：** [点击跳转至本题][Link 5]

**题目大意：  
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。(如给定 1->2->3->4, 你应该返回 2->1->4->3；要求是实际的进行节点交换。)**

**解题思路：`哨兵节点`\+`迭代`**  
设置一个哨兵节preHead点方便结果的返回，并使用prev作为它的工作指针。  
两两交换时有关键的三步：  
**①prev节点向后链接上head节点的下一个节点。**  
![在这里插入图片描述][20200721215906194.png]

**②head节点向后链接上head节点的下一个节点的下一个节点。**  
![在这里插入图片描述][20200721215947205.png]  
**③prev节点的下一个节点向后链接上head节点。**  
![在这里插入图片描述][20200721220025856.png]  
此时，完成了一个两两交换，接下来需要更新head和prev的位置继续进行下一次交换：

//位置的更新依据是：head节点作为两两交换的第一个节点，prev在head节点的前一位。
            prev = head;
            head = head.next;

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode swapPairs(ListNode head) { 
            //创建哨兵节点
            ListNode preHead = new ListNode(-1);
            //哨兵节点指向链表头节点head
            preHead.next = head;
            //prev节点代替哨兵节点工作
            ListNode prev = preHead;
            while ((head != null) && (head.next != null)) { 
                //两两交换
                prev.next = head.next;
                head.next = head.next.next;
                prev.next.next = head;
    
                prev = head;
                head = head.next; // jump
            }
            return preHead.next;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 5]

### 61. 旋转链表 ###

**题目链接：** [点击跳转至本题][Link 6]

**题目大意：  
给定一个链表，要求旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 6]

**解题思路：`单链表⬅(转换)➡环形链表`**  
整体思路是先将链表合并成环形链表，根据给出的k找到新的链表头和链表尾，断开这个环。当k<lengh时断开的位置应该为length-k；当k>length时断开的位置应该为length-k%length。两者可以合并为length-k%length。代码实现时是依据下标，length-k%lengt-1即可。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode rotateRight(ListNode head, int k) { 
            //特判情况
            if(head == null){ 
                return null;
            }
            if(head.next == null){ 
                return head;
            }
            //定义length记录链表长度
            int length = 0;
            //将单链表转换为环形链表
            ListNode p = head;
            while(p.next!=null){ 
                p = p.next;
                length++;
            }
            length++;
            p.next = head;
            //找到该断开的位置
            ListNode q = head;
            for(int i=0;i < length - k % length - 1;i++){ 
                q = q.next;
            }
            //使断开处的右节点作为新的头节点
            ListNode newHead = q.next;
            //将断开处的左节点作为尾节点
            q.next = null;
            return newHead;
        }
    }

### 82. 删除排序链表中的重复元素 II ###

**题目链接：** [点击跳转至本题][Link 7]

**题目大意：  
给定一个排序链表，要求删除所有含有重复数字的节点，只保留原始链表中没有重复出现 的数字。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 7]

**解题思路：`哨兵节点+双指针`**  
创建哨兵节点preHead，使其下一个节点连接到head上。再创建a节点代替preHead节点移动，b节点代替head节点移动，因此比较逻辑是a的下一个节点和b的下一个节点。在遍历时，当a的下一个节点等于b的下一个节点时，就不断的移动b，直到两者不相等，此时，令a的下一个节点连接上b的下一个节点，b后移，为下一次判断做准备；当a的下一个节点不等于b的下一个节点时，a与b都后移即可。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode deleteDuplicates(ListNode head) { 
            //创建哨兵节点
            if(head == null || head.next == null){ 
                return head;
            }
            ListNode preHead = new ListNode(-1);
            preHead.next = head;
            ListNode a = preHead;
            ListNode b = head;
            while(b != null && b.next != null){ 
                /** 因为a是哨兵节点且为哑节点,所以比较逻辑是a的下一个节点和b的下一个节点. 如果a,b指向的节点值相等,就不断移动b,直到a,b指向的值不相等; 否则不相等,则都向后移 **/
                if(a.next.val == b.next.val){ 
                    while(b!=null && b.next!=null && a.next.val == b.next.val){ 
                        b = b.next;
                    }
                    a.next = b.next;
                    b = b.next;
                }else if(a.next.val != b.next.val){ 
                    a = a.next;
                    b = b.next;
                }
            }
            return preHead.next;
        }
    }

### 86. 分隔链表 ###

**题目链接：** [点击跳转至本题][Link 8]

**题目大意：  
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。应当保留两个分区中每个节点的初始相对位置(即不需要排序)。**

**解题思路：双哨兵节点**  
设置两个哨兵节点，遍历时，将小于特定值x的节点链接到一个新的链表上，将大于等于特定值x的节点链接到另一个新的链表上，最后将第二个链表链接到第一个链表上。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode partition(ListNode head, int x) { 
            //链表L记录小于x的元素
            ListNode L = new ListNode(0);
            ListNode preL = L;
            //链表R记录大于等于x的元素
            ListNode R = new ListNode(0);
            ListNode preR = R;
            
            while(head != null){ 
                if(head.val < x){ 
                    preL.next = new ListNode(head.val);
                    preL = preL.next;
                }else{ 
                    preR.next = new ListNode(head.val);
                    preR = preR.next;
                }
                head = head.next;
            }
            //拼接两段链表
            preL.next = R.next;
            return L.next;
        }
    }

## 困难 ##

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

**题目链接：** [点击跳转至本题][Link 9]

**题目大意：  
合并 k 个排序链表，返回合并后的排序链表。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 8]

**解题思路：**  
两两合并，将第一个与最后一个，第二个与倒数第二个合并。合并一次后，新的链表分布在第1到(k+1)/2个链表中，继续这样的合并，直到新的链表只在数组第一个位置。此时返回数组的第一个元素，即合并之后的链表。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 9]

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode mergeKLists(ListNode[] lists) { 
            int len = lists.length;
            if (len == 0) { 
                return null;
            }    
            // 将n个链表以中间为对称，合并，即合并 
            while(len>1) { 
                for (int i=0; i<len/2; i++) { 
                    lists[i] = mergeTwoLists(lists[i], lists[len-1-i]);
                }
                len = (len+1)/2;
            }
            return lists[0];
        }
        
        // 合并两个链表
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
            ListNode head = new ListNode(-1);
            ListNode p = head;
            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;
            }
            if (l1 != null) { 
                p.next = l1;
            } else if (l2 != null) { 
                p.next = l2;
            }
            return head.next;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70]: /images/20230209/ed652379cda348cca6b117782b7284c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200727203319792.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 1]: https://leetcode-cn.com/problems/merge-two-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200721151746717.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 2]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
[2020072416044483.png]: https://img-blog.csdnimg.cn/2020072416044483.png
[Link 3]: https://leetcode-cn.com/problems/add-two-numbers/
[20200721023625281.png]: https://img-blog.csdnimg.cn/20200721023625281.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200721025548343.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 4]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200721155948257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 5]: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
[20200721215906194.png]: https://img-blog.csdnimg.cn/20200721215906194.png
[20200721215947205.png]: https://img-blog.csdnimg.cn/20200721215947205.png
[20200721220025856.png]: https://img-blog.csdnimg.cn/20200721220025856.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200721214350177.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 6]: https://leetcode-cn.com/problems/rotate-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200724170826149.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 7]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200724160412460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[Link 8]: https://leetcode-cn.com/problems/partition-list/
[Link 9]: https://leetcode-cn.com/problems/merge-k-sorted-lists/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200726214454914.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200726215027108.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA==,size_16,color_FFFFFF,t_70