LeetCode刷题第六周

喜欢ヅ旅行 2023-03-03 15:28 27阅读 0赞

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

> 听说开学又要延期了！

### 文章目录 ###

*  链表专题
 *   *  简单
     *   *  141. 环形链表
         *  160. 相交链表
         *  203. 移除链表元素
         *  206. 反转链表
         *  234. 回文链表
         *  237. 删除链表中的节点
     *  中等
     *   *  92. 反转链表 II
         *  142. 环形链表 II
         *  148. 排序链表
         *  328. 奇偶链表

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

# 链表专题 #

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

## 简单 ##

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

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

**题目大意：  
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。**

**解题思路：**  
方法1：`二倍追击（推荐）`  
判断链表是否有环，可以设置快慢指针同时从链表首元节点开始移动，慢指针每次移动一步，快指针每次移动两步。只要两指针相遇，那就一定是一个环。

方法2：`哈希表`  
用散列表HashSet记录走过的结点，如果出现重复则说明走回来了，成环。

//方法1：双指针追击
    public class Solution { 
        public boolean hasCycle(ListNode head) { 
            //定义快慢指针
            ListNode slow = head;
            ListNode fast = head;
            while(slow != null && fast != null && fast.next !=null){ 
                //慢指针每次走一步
                slow = slow.next;
                //快指针每次走两步
                fast = fast.next.next;
                //相遇即是环
                if(slow == fast){ 
                    return true;
                }
            }
            return false;
        }
    }
    
    //方法2：散列表
    public class Solution { 
        public boolean hasCycle(ListNode head) { 
             Set<ListNode> node = new HashSet<>();
             while(head!=null){ 
                if(node.contains(head)){ 
                     return true;
                 }else{ 
                     node.add(head);
                 }
                 head = head.next;
             }
             return false;
        }
    }

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

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

**题目大意：  
给定两个链表，要求返回两个链表相交的起始节点，若无相交节点则返回null。**

**解题思路：`浪漫指针`**  
在做[141. 环形链表][Link 1]时，判断是否是环形链表的方法是双指针二倍追击，如果相遇即是环；本题判断相交链表仍然使用双指针追击，暂且叫他浪漫指针。两链表判相交，可以让链表分别走到尽头，然后分别走另一条链表走过的路线。此时若再相遇，即是相交。

/** * 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) { 
            //特判:是空链表时直接返回
            if(headA == null || headB == null){ 
                return null;
            }
            //定义两个链表的工作指针
            ListNode pA = headA,pB = headB;
            //走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
            while(pA != pB){ 
                pA = pA == null ? headB:pA.next;
                pB = pB == null ? headA:pB.next;
            }
            return pA;
        }
    }

### 203. 移除链表元素 ###

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

**题目大意：给定一个链表，要求删除链表中等于给定值 val 的所有节点。**

**解题思路：`哨兵节点+快慢指针`**  
删除链表元素中值等于val的节点，看起来似乎很简单，但当要删除的一个或多个节点位于链表的头部时，就会变得很复杂。为此可以采用快慢指针，pre1作为慢指针，pre2作为快指针，每次都让pre2和val进行判断，然后让pre1的下一个节点连接到pre2的下一个节点。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode removeElements(ListNode head, int val) { 
            //设置哨兵节点
            ListNode preHead = new ListNode(0);
            preHead.next = head;
            //pre1，pre2为工作指针
            ListNode pre1 = preHead,pre2 = head;
            while(pre2 != null){ 
                if(pre2.val == val){ 
                    pre1.next = pre2.next;
                }else{ 
                    pre1 = pre2;
                }
                pre2 = pre2.next;
            }
            return preHead.next;
        }
    }

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

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

**题目大意：反转一个链表**  
![在这里插入图片描述][20200802222303945.png]

**解题思路：`双指针迭代`**  
反转一个单链表需要借助一个pre节点、cur节点、tmp节点。其中pre节点始终指向新的链表的链表头，cur节点对当前链表做遍历，tmp节点对当前节点的下一个节点做保存。题目比较经典，建议数量掌握。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode reverseList(ListNode head) { 
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null){ 
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }
    }

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

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

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

**题目大意：判断一个链表是否为回文链表。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 3]

**解题思路：`双指针迭代反转链表+双指针二倍追击`**  
考虑使用二倍追击得到链表中间节点（中间靠右的节点），此时将链表的后半段进行反转。然后比较给出的链表与反转得到的链表。

/** /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public boolean isPalindrome(ListNode head) { 
            //特判:空链表或只有一个节点直接返回true
            if(head == null || head.next ==null){ 
                return true;
            }
    
            //end表示前后半段链表的头节点
            ListNode end = halfList(head);
            //L表示对链表后半段反转后的链表
            ListNode L = reverseList(end);
            
            //判断是否相等
            ListNode p1 = head;
            ListNode p2 = L;
            boolean result = true;
            while(result && p2 != null){ 
                if(p1.val != p2.val) { 
                    result = false;
                }
                p1 = p1.next;
                p2 = p2.next;
            }
            //可以考虑将链表还原
            //end = reverseList(L);
            return result;
        }
    
        /** 反转链表 pre节点指向新链表的头 cur为遍历节点 tmp保存cur下一个节点的值 **/
        private ListNode reverseList(ListNode head){ 
            ListNode pre = null;
            ListNode cur = head;
            while(cur != null){ 
                ListNode tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            }
            return pre;
        }
    
        /** 二倍追击 返回的slow代表后半段链表的起始节点 **/
        private ListNode halfList(ListNode head){ 
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){ 
                fast = fast.next.next;
                slow = slow.next;
            }
            return slow;
        }
    }

### 237. 删除链表中的节点 ###

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

**题目大意：写一个方法，删除当前节点。  
注意：当前节点非末尾节点。**

**解题思路：`与下一个节点交换`**  
本题只是要求写一个方法删除当前节点，可以将下一个节点的值赋给当前节点，然后删除下一个节点。而在[203. 移除链表元素][Link 3]中，是给出了链表的头节点和待删除节点的。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public void deleteNode(ListNode node) { 
            //将后一个节点的val赋给node
            node.val = node.next.val;
            //删除node后面的节点
            node.next = node.next.next;
        }
    }

## 中等 ##

### 92. 反转链表 II ###

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

**题目大意：  
反转从位置 m 到 n 的链表。  
说明:1 ≤ m ≤ n ≤ 链表长度。要求使用一趟扫描完成反转**  
![在这里插入图片描述][20200731215931956.png]

**解题思路：`哨兵节点+快慢指针`**  
如下图，定义快慢指针p和q。首先，将p移动到m节点的前一个节点，q在m处，然后开始遍历n-m次，每次的操作过程可参照代码和图示理解。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 4]

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode reverseBetween(ListNode head, int m, int n) { 
            //设置哨兵节点
            ListNode preHead = new ListNode(0);
            preHead.next = head;
            //p作为慢指针,q作为快指针
            ListNode p = preHead;
            ListNode q = preHead.next;
            //将p移动到m节点的前一个节点
            int num = 0;
            while(num < m - 1){ 
                p = p.next;
                q = q.next;
                num++;
            }
            //将q从m处遍历到n处
            for(int i=0;i<n-m;i++){ 
                //定义temp节点保存q.next节点
                ListNode temp = q.next;
                //删除q.next节点
                q.next = q.next.next;
                //temp节点连接上p.next节点
                temp.next = p.next;
                //p.next连接上temp节点
                p.next = temp;
            }
            return preHead.next;
        }
    }

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

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

**题目大意：  
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。**

**解题思路：`HashSet`**  
本题可以使用双指针进行快慢追击，但是过于复杂，这里使用不可重复的集合HashSet来进行比较判断，当下一个将要添加到set的节点已经存在再set中的时候，返回下一个节点。

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
    public class Solution { 
        public ListNode detectCycle(ListNode head) { 
            //HashSet是不可以重复的集合
            Set<ListNode> set = new HashSet<ListNode>();
    
            ListNode node = head;
            while (node != null) { 
                //如果出现重复，就返回第二个节点
                if (set.contains(node)) { 
                    return node;
                }
                //依次将每一个节点加入set集合
                set.add(node);
                node = node.next;
            }
            return null;
        }
    }

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

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

**题目大意：  
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。**

**解题思路：`归并排序`**  
链表使用归并排序，主要有分解和合并两个环节：

分解操作：

*  找到链表中点并断开（使用块面快慢指针法，奇数个节点时slow是中点，偶数个节点时slow是中点左边的节点）。
 *  找到中点slow后，将链表切断（slow.next=null;）。
 *  递归分解时，输入当前链表的左端点head和中心节点slow的下一个节点head2。
 *  递归终止条件是head.next==null。

合并操作：

*  将两个有序链表合并，转化为一个有序链表。
 *  设置left，right分别指向两链表头部，比较指针处节点值大小，由小到大加入哨兵节点中的工作节点中。
 *  返回哨兵节点的下一个节点。

注意：使用归并排序时，链表可以通过修改引用来更改节点顺序，所以无需像数组一样开辟额外空间。

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

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        /* head slow | head2 fast */
        public ListNode sortList(ListNode head) { 
            //特判:只有0个或1个节点的链表
            if(head == null ||head.next == null){ 
                return head;
            }
            //二倍追击，最终使slow落在中间，fast到达结尾
            ListNode slow = head,fast = head.next;
            while(fast !=null && fast.next!=null){ 
                slow = slow.next;
                fast = fast.next.next;
            }
            //定义head2表示右边的有序数据
            ListNode head2 = slow.next;
            //左边有序数据从slow.next断开
            slow.next = null;
            //下两行是递归分解
            ListNode left = sortList(head);
            ListNode right = sortList(head2);
            //创建哨兵节点，方便存储结果
            ListNode preHead = new ListNode(0);
            ListNode pre = preHead;
            /** 下面是合并操作 **/
            //1.先把左右两边(有序)的数据按照规则链接到pre后
            while(left != null && right !=null){ 
                if(left.val < right.val){ 
                    pre.next = left;
                    left = left.next;
                }else{ 
                    pre.next = right;
                    right = right.next;
                }
                pre = pre.next;
            }
            // 2.把有剩余数据的一边的数据依次链接到pre后
            pre.next = left !=null ?left:right;
            return preHead.next;
        }
    }

### 328. 奇偶链表 ###

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

**题目大意：  
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。**

**解题思路：`首尾指针`**  
分别定义奇偶链表的头尾节点，可以将head直接作为奇链表的头，再额外定义其他三个指针。一次遍历，将奇节点都放在奇链表中，偶节点都放在偶链表中，最后将偶链表链接在奇链表尾部。

/** * 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 oddEvenList(ListNode head) { 
            if(null == head){ 
                return null;
            }
            //head表示奇链表的头,odd表示奇链表工作指针;evenHead表示偶链表头,even表示偶链表工作指针
            ListNode odd = head;
            ListNode evenHead = head.next;
            ListNode even = evenHead;
            while(even != null && even.next != null){ 
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70]: /images/20230208/7296f06044bd4c2d891fd3ddd71e5cd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 1]: /images/20230208/725eb397acfd47ba8bb35133f7a0852f.png
[Link 1]: https://leetcode-cn.com/problems/linked-list-cycle/
[Link 2]: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
[Link 3]: https://leetcode-cn.com/problems/remove-linked-list-elements/
[Link 4]: https://leetcode-cn.com/problems/reverse-linked-list/
[20200802222303945.png]: /images/20230208/9459c581a622421e9dc9ceb25ca95ada.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 2]: /images/20230208/54e909f2ed6346e685eab673c8bc0db3.png
[Link 5]: https://leetcode-cn.com/problems/palindrome-linked-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 3]: /images/20230208/fc998b15cbae4da89c05ceedd70beb9d.png
[Link 6]: https://leetcode-cn.com/problems/delete-node-in-a-linked-list/
[Link 7]: https://leetcode-cn.com/problems/reverse-linked-list-ii/
[20200731215931956.png]: /images/20230208/7cecee74df044a75b5b1f2e889d4b7ef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 4]: /images/20230208/864a8f5d2d124f05a574b970782562cd.png
[Link 8]: https://leetcode-cn.com/problems/linked-list-cycle-ii/
[Link 9]: https://leetcode-cn.com/problems/sort-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY5MTA1OA_size_16_color_FFFFFF_t_70 5]: /images/20230208/ac4e23ef647c4ba9bf12233cdeab99b8.png
[Link 10]: https://leetcode-cn.com/problems/odd-even-linked-list/