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

    四、链表

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

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

    原题链接
    在这里插入图片描述

    给定一个链表，删除链表的倒数第 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，那么慢指针指向的结点就是待删除结点的前一个结点

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

    /**
 * 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 removeNthFromEnd(ListNode head, int n) {
        if(head.next == null) return null;

        //增加一个哑结点
ListNode temp = new ListNode();
temp.next = head;
     ListNode fast = temp, slow = temp;

     while(n-- > 0){
         fast = fast.next;
     }

     while(fast.next != null)
{
    fast = fast.next;
    slow = slow.next;
}

slow.next = slow.next.next;

return temp.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

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

    原题链接

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

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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;
         

    }
}

    • 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

    4.3反转链表

    原题链接

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

    示例 1：
    在这里插入图片描述

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

    提示：

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

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

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

    解法1：非递归

    /**
 * 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 reverseList(ListNode head) {

        if(head == null || head.next == null) return  head;
           
         ListNode pr = head;
         ListNode q = null;
while(pr != null){

 //挂起 pr 后的链表
    ListNode temp =  pr.next;
   
    //反转  
    pr.next = q;

    // 指向移动
    q = pr;
    pr = temp;

}

return q;
              
            
    }
}

    • 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

    解法2：递归

    /**
 * 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 reverseList(ListNode head) {

  if( head ==null || head.next == null) return head;

  ListNode newhead = reverseList(head.next);

   // head 是结点4  5 -> 4
    head.next.next = head;
    // 4 -> null  防止出现环
    head.next = null;


    return newhead;

     
    }
}

    • 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

    4.4链表中环的入口结点

    原题链接

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

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

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

    示例 1：

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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;
    }
}

    • 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

    解法二： 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;
     

    }
}

    • 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

    4.5 链表中两数之和

    原题链接

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

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

    示例1：

    在这里插入图片描述

    • 输入：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;
    }
}

    • 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

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

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

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

    • 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

    4.6重排链表

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

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

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

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

    示例 1:

    在这里插入图片描述

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

    提示：

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

    解法一：

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

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

    /**
 * 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 void reorderList(ListNode head) {

   Deque<ListNode> queue = new LinkedList<>();
   ListNode cur = head;
   while(cur != null){
       queue.offer(cur);
       cur = cur.next;
   }

   cur = head;
   for(int i = 0; !queue.isEmpty();i++,cur = cur.next){
       cur.next = i % 2 == 0 ? queue.removeFirst():queue.removeLast();
   }

   cur.next = null;

    }
}

    • 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

    解法二

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

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

    /**
 * 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 void reorderList(ListNode head) {

   ListNode fast = head, slow = head;
   while(fast.next != null && fast.next.next != null){
       slow = slow.next;
       fast = fast.next.next;
   }

//临时指针指向中间结点的下一个结点 挂起链表
   ListNode temp = slow.next;
        
        //反转链表
        ListNode p = null;

        while(temp != null){
            temp = slow.next;
            slow.next = p;

            p = slow;
            slow = temp;
        }

         //开始合并
     ListNode pr = head;

       while(pr != null){
          temp = pr.next;
          pr.next = p;

         pr = p;
         p = temp;

      }
    

    }
}

    • 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

    4.7回文链表

    原文链接

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

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

    示例 1：

    在这里插入图片描述

    • 输入: 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;


    }
}

    • 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

    4.8排序的循环链表

    原题链接

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

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

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

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

    示例 1：

    在这里插入图片描述

    • 输入：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;


    }
}

    • 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
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81

    4.9 展开多级双向链表

    原题链接

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

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

    示例 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-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);
    }
}

    • 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

    持续更新中…

  • 相关阅读:
    java计算机毕业设计高校人事管理系统源码+数据库+系统+lw文档+部署
    模板进阶：非类型模板参数，特化
    MapReduce Shuffle源码解读
    OceanBase开源TB级别分布式关系型数据库OceanBase理论详解
    面试题-React(八)：React如何实现插槽？
    基于C#开放式TCP通信建立与西门子PLC的socket通信示例
    北理工嵩天Python语言程序设计笔记（6 函数和代码复用）
    【21天学习挑战赛】KMP模式匹配算法
    Spring框架对BeanUtils.copyProperties的优化
    Lingo基础语法笔记
  • 原文地址：https://blog.csdn.net/qq_52595134/article/details/127855753