链表——算法专项刷题（四）

超、凢脫俗 2024-04-01 18:41 41阅读 0赞

### 四、链表 ###

链表常用算法及思想：快慢指针、哈希表  
注意点：注意链表的边界情况，如头结点

#### 4.1删除链表的倒数第n个结点 ####

[原题链接][Link 1]  
![在这里插入图片描述][0fdf31ad89af40e4ae04119f91d11fe9.png]

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

*  输入：head = \[1,2,3,4,5\], n = 2
 *  输出：\[1,2,3,5\]

**提示：**

*  链表中结点的数目为 `sz`
 *  `1 <= sz <= 30`
 *  `0 <= Node.val <= 100`
 *  `1 <= n <= sz`

**思路：** 快慢指针，先让快指针走n步，然后快慢指针一块遍历链表，如果快指针指向的结点的下一个结点为null，那么慢指针指向的结点就是待删除结点的前一个结点

**注意点：** 链表结点删除注意删除头结点的情况，可以设置一个哑结点

#### 4.2 两个链表的第一个重合结点 ####

[原题链接][Link 2]

给定两个单链表的头节点 `headA` 和 `headB` ，请找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 `null` 。

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zQcsizaH-1668431477933)(D:/picture/picture/img/image-20221111183004967.png)\]][img-zQcsizaH-1668431477933_D_picture_picture_img_image-20221111183004967.png]

**输入：** intersectVal = 8, listA = \[4,1,8,4,5\], listB = \[5,0,1,8,4,5\], skipA = 2, skipB = 3

**输出：** Intersected at ‘8’

*  解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
 *  从各自的表头开始算起，链表 A 为 \[4,1,8,4,5\]，链表 B 为 \[5,0,1,8,4,5\]。
 *  在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

**思路：** 两个指针分别遍历两个单链表，遍历结束就去遍历另一个单链表，如果存在相遇点那么第二次遍历两个指针会相遇

**注意点：** 需要考虑不存在相遇点的情况，使用一个变量记录状态

/**
     * 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) {
        
            
                 ListNode p1 = headA;
                 ListNode p2 = headB;
    
    if(p1 == p2) return p1;
                 
             // 0 表示两个指针还没有遍历另一个链表
                   int idx = 0;
    
                 while(p1 != null){
        
                     
                     // 当idx = 1 时说明以及遍历另一个链表了，那么如果p1还等于null 那么就说明没有相  //遇点
                     if(p1.next == null && idx == 0){
        
                        p1 =  headB;
                        idx = 1;
                     }else{
        
                         p1 = p1.next;
                     }
                    
    
                     p2 = p2.next == null ? headA : p2.next;
    
                     if(p1 == p2) return p1;
                       
    
                 }
    
                 return null;
             
    
        }
    }

#### 4.3反转链表 ####

[原题链接][Link 3]

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

**示例 1：**  
![在这里插入图片描述][bc8c1a0a5dff47f0842b93c9bcfaf7e0.png]

*  输入：head = \[1,2,3,4,5\]
 *  输出：\[5,4,3,2,1\]

**提示：**

*  链表中节点的数目范围是 `[0, 5000]`
 *  `-5000 <= Node.val <= 5000`

**思路：** 可以有递归或者非递归，两个指针遍历一遍链表将每一个结点反转

**注意点：** 在操作链表时注意指向，必要是需要使用临时指针挂起链表

解法1：非递归

解法2：递归

#### 4.4链表中环的入口结点 ####

[原题链接][Link 4]

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，**pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中**。

**说明：** 不允许修改给定的链表。

**示例 1：**

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-W8Aed9VO-1668431477936)(D:/picture/picture/img/circularlinkedlist.png)\]][img-W8Aed9VO-1668431477936_D_picture_picture_img_circularlinkedlist.png]

*  输入：head = \[3,2,0,-4\], pos = 1
 *  输出：返回索引为 1 的链表节点
 *  解释：链表中有一个环，其尾部连接到第二个节点。

**提示：**

*  链表中节点的数目范围在范围 `[0, 104]` 内
 *  `-10^5 <= Node.val <= 10^5`
 *  `pos` 的值为 `-1` 或者链表中的一个有效索引

**解法一：** O(n)空间 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) {
        
            
    //set 存储结点
            Set<ListNode> set = new HashSet();
    
            ListNode p = head;
    
            while(p != null){
        
                if(set.contains(p)){
        
                    return p;
                }else{
        
                    set.add(p);
                }
                p = p.next;
            }
    
            return null;
        }
    }

**解法二：** O(1)空间 快慢指针

思路：快慢指针，快指针速度是慢指针的二倍，如果不存在环则返回null，若存在环，当快慢指针第一次相遇时，快指针从头结点再来并且速度变成和慢指针相同，当快慢指针再次相遇时，就是在环的入口

/**
     * 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) {
        
            
    
    ListNode fast = head;
    ListNode slow = head;
    
             while(fast != null && fast.next != null){
        
                 fast = fast.next.next;
                 slow = slow.next;
    
                 //快慢指针相遇 
                 if(fast == slow){
        
                     // 快指针从头再来
                     fast = head;
                     while(slow != fast){
        
                         //快慢指针同步进行移动
                         fast = fast.next;
                         slow = slow.next;
                     }
                     // 快慢指针相遇在环的入口点
                     return slow;
                 }
             }
    
             //没有环
             return null;
         
    
        }
    }

#### 4.5 链表中两数之和 ####

[原题链接][Link 5]

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

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

**示例1：**

![在这里插入图片描述][c97802f91e214d2a8c873345dc2dfd29.png]

*  输入：l1 = \[7,2,4,3\], l2 = \[5,6,4\]
 *  输出：\[7,8,0,7\]

**提示：**

*  链表的长度范围为`[1, 100]`
 *  `0 <= node.val <= 9`
 *  输入数据保证链表代表的数字无前导 0

解法一：反转链表+模拟

思路：将两个链表反转，然后模拟加法 最后再把新链表反转

/**
     * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        
            //反转两个链表
            ListNode L1=reverselist(l1);
            ListNode L2=reverselist(l2);
            
            //创建新的哑结点
            ListNode res=new ListNode();
            ListNode cur=res;
            
            //进位
            int idx=0;
            while(L1 != null || L2 != null){
        
                int num1= L1 == null ? 0 : L1.val;
                int num2= L2 == null ? 0 : L2.val;
                int sum= num1 + num2 + idx;
                //存储新结点
                cur.next=new ListNode(sum % 10);
                
                idx = sum/10;
                L1= L1 == null ? null: L1.next;
                L2= L2 == null ? null: L2.next;
                cur = cur.next;
            }
            //判断最高位是否有进位
            if(idx == 1) cur.next = new ListNode(1);
            //将结果反转返回
            return reverselist(res.next);
        } 
        
         
        public ListNode reverselist(ListNode l){
        
            ListNode pre=null;
            ListNode cur=l;
            while(cur!=null){
        
                ListNode temp=cur.next;
                cur.next=pre;
                pre=cur;
                cur=temp;
            }
            return pre;
        }
    }

解法二：辅助栈+模拟加法

思路：使用两个辅助栈，将链表的结点压入栈中，然后弹出栈顶元素进行加法

/**
     * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        
            //辅助栈
            Deque<Integer> s1=new ArrayDeque<>();
            Deque<Integer> s2=new ArrayDeque<>();
            
            ListNode n1 = l1;
            ListNode n2 = l2;
    
            ListNode res = null;
            while(n1 != null){
        
                s1.push(n1.val);
                n1=n1.next;
            } 
            while(n2 != null){
        
                s2.push(n2.val);
                n2=n2.next;
            }
            int idx = 0;
            // 辅助栈不为空 或者进位不为空
            while(!s1.isEmpty() || !s2.isEmpty() || idx != 0){
        
                int num1= s1.isEmpty()? 0 :s1.pop();
                int num2= s2.isEmpty()? 0: s2.pop();
                int cur=num1+num2+idx;
                idx = cur/10;
                cur = cur % 10;
                ListNode temp = new ListNode(cur);
                temp.next = res;
                res = temp;
            }
            return res;
        }
    }

#### 4.6重排链表 ####

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln  
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

**示例 1:**

![在这里插入图片描述][ba2fe222757e415f9fc9ff2c22e17a94.png]

输入: head = \[1,2,3,4\]  
输出: \[1,4,2,3\]

**提示：**

*  链表的长度范围为 `[1, 5 * 104]`
 *  `1 <= node.val <= 1000`

解法一：

思路：双端队列，把链表结点都存入队列中，遍历队列结点，如果遍历的次数是偶数，就接队列头的结点。如果遍历的次数是奇数，就接队列的尾部的结点

注意：最后结点的下一个节点是null，不然就形成环了

解法二

思路：找中间结点 + 反转 + 重连

注意：在进行反转和重连时，注意结点的的指向需要用临时指针存储，不能丢失指向

#### 4.7回文链表 ####

[原文链接][Link 6]

给定一个链表的 **头节点** `head` \*\*，\*\*请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

**示例 1：**

![在这里插入图片描述][3db3f903be204c308da37921554ad614.png]

*  输入: head = \[1,2,3,3,2,1\]
 *  输出: true

**提示：**

*  链表 L 的长度范围为 `[1, 105]`
 *  `0 <= node.val <= 9`

思路：折半反转+回文判断

注意点：注意边界条件，反转链表时的指向

/**
     * 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 boolean isPalindrome(ListNode head) {
        
    
            if(head == null || head.next == null) return true;
        
          ListNode fast = head;
          ListNode slow = head;
         
      // 找链表的中点结点
          while(fast != null && fast.next != null){
        
              fast = fast.next.next;
              slow = slow.next;
             
          }     
    
         ListNode p = slow;
         ListNode pr = null;
    
            // 反转链表
         while(p != null){
        
             //挂起链表
             ListNode temp = p.next;
                p.next = pr;
    
                pr = p;
    
                p = temp;
    
         }
    
            //  1->2->3-> null<-3<-2<-1 
           ListNode q = pr;
           
         while(q != null){
        
             if(q.val != head.val) return false;
    
             q = q.next;
             head = head.next;
            
         }
          
           return true;
    
    
        }
    }

#### 4.8排序的循环链表 ####

[原题链接][Link 7]

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

**示例 1：**

![在这里插入图片描述][b88c1066106443fd884ce761aace3210.png]

*  输入：head = \[3,4,1\], insertVal = 2
 *  输出：\[3,4,1,2\]
 *  解释：在上图中，有一个包含三个元素的循环有序列表，你获得值为 3 的节点的指针，我们需要向表中插入元素 2 。新插入的节点应该在 1 和 3 之间，插入之后，整个列表如上图所示，最后返回节点 3 。

**提示：**

*  `0 <= Number of Nodes <= 5 * 10^4`
 *  `-10^6 <= Node.val <= 10^6`
 *  `-10^6 <= insertVal <= 10^6`

**思路：** 找到待插入结点的位置，通过一次遍历求得链表得最大值 max 和最小值 min

*  原链表为空 创建循环链表
 *  min =< insertVal <= max
 *  insertVal > max || insertVal < min

**注意点：** 去重

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node next;
    
        public Node() {}
    
        public Node(int _val) {
            val = _val;
        }
    
        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    };
    */
    
    class Solution {
        
        public Node insert(Node head, int insertVal) {
        
    
            Node res = new Node(insertVal);
    
    //空链表
            if(head == null) {
        
                res.next = res;
                return res;
            }
            
            
    
          Node p = head.next;
         
    
          int max = head.val, min = head.val;
    
          while(p != head){
        
              max = Math.max(p.val, max);
              min = Math.min(p.val, min);
              p = p.next;
          }
    
          p = head;
    
          
    
    //min == max 任意位置
          if(min == max){
        
            
          
    
          }else if( insertVal > max || insertVal < min ){
        
              //在分界位置
    
               //去重
              while(p.val != max || p.val == p.next.val  ){
        
                  p = p.next;
              }
              
          }else{
        
          
            while(true ){
        
                if(p.val <= insertVal && p.next.val >= insertVal) break;
    
                p = p.next;
            }  
         
          }
    
            // 插入结点
             Node temp = p.next;
              p.next = res;
              res.next = temp;
    
    
    return head;
    
    
        }
    }

#### 4.9 展开多级双向链表 ####

[原题链接][Link 8]

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

**示例 1：**

*  输入：head = \[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12\]
 *  输出：\[1,2,3,7,8,11,12,9,10,4,5,6\]

**解释：**

输入的多级列表如下图所示：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VKgXvyeu-1668690384910)(D:/picture/picture/img/image-20221117205712688.png)\]][img-VKgXvyeu-1668690384910_D_picture_picture_img_image-20221117205712688.png]

扁平化后的链表如下图：

![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gtt7t1Pr-1668690384910)(D:/picture/picture/img/image-20221117205701761.png)\]][img-gtt7t1Pr-1668690384910_D_picture_picture_img_image-20221117205701761.png]

**提示：**

*  节点数目不超过 `1000`
 *  `1 <= Node.val <= 10^5`

**思路：** 利用dfs 将链表结点存入list集合中，然后进行连接

**注意点：** dfs中先遍历孩子结点，再遍历下一个结点

/*
    // Definition for a Node.
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    };
    */
    
    class Solution {
        
    
        List<Node> list = new ArrayList();
        public Node flatten(Node head) {
        
            
            dfs(head);
    
              int size = list.size() - 1;
            for(int i= 0; i < size; i++ ){
        
    
                Node p1 = list.get(i);
    
                Node p2 = list.get(i+1);
                 p2.prev = p1;
                
                p1.next = p2;
                        
                p1.child = null;
                p2.child = null;
    
            }
            
            return head;
    
            
        }
    
        void dfs(Node head){
        
            if(head == null) return;
            list.add(head);
     //先遍历孩子结点
            dfs(head.child);
            dfs(head.next);
        }
    }

持续更新中…

[Link 1]: https://leetcode.cn/problems/SLwz0R/
[0fdf31ad89af40e4ae04119f91d11fe9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/758677a0e88f42f6a3aecb8dcda53173.png
[Link 2]: https://leetcode.cn/problems/3u1WK4/
[img-zQcsizaH-1668431477933_D_picture_picture_img_image-20221111183004967.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/970f0046ce4348cea91cb59539bcd1b5.png
[Link 3]: https://leetcode.cn/problems/UHnkqh/
[bc8c1a0a5dff47f0842b93c9bcfaf7e0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/f090a9693379405b9f9be94f57ffca7e.png
[Link 4]: https://leetcode.cn/problems/c32eOV/
[img-W8Aed9VO-1668431477936_D_picture_picture_img_circularlinkedlist.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/3e02fde16adf4a2f95c6a523ef75e39b.png
[Link 5]: https://leetcode.cn/problems/lMSNwu/
[c97802f91e214d2a8c873345dc2dfd29.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/d53da957683f4701a0533a12953cc96c.png
[ba2fe222757e415f9fc9ff2c22e17a94.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/15c60783a1844ecc8bb01d750da06618.png
[Link 6]: https://leetcode.cn/problems/aMhZSa/
[3db3f903be204c308da37921554ad614.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/6d177d2d1c544eac94a0804078199a76.png
[Link 7]: https://leetcode.cn/problems/4ueAj6/
[b88c1066106443fd884ce761aace3210.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/bb94654f72174ec5b1e9e3cd074af164.png
[Link 8]: https://leetcode.cn/problems/Qv1Da2/
[img-VKgXvyeu-1668690384910_D_picture_picture_img_image-20221117205712688.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cc5acc76c0da44d5b5d16976bcbb4348.png
[img-gtt7t1Pr-1668690384910_D_picture_picture_img_image-20221117205701761.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/88abacca2f5a4304a975e90c2d34870e.png