Session 24: Linked List 3

Original Session

Date: 29 Dec 2024

Topic: Linked List 3

Concept: Linked List

1. 25. Reverse Nodes in k-Group
   1. leetcode here

   public ListNode reverseKGroup(ListNode head, int k) {
           
           if (head == null || head.next == null || k== 1) {
               return head;
           }
   
           ListNode curr = head;
           int len = 0;
           while (curr != null) {
   
               curr = curr.next;
               len ++;
           }
           curr = head;
           ListNode prev = null, next = null;
           ListNode newHead = null, t1 = null, t2 = head;
   
           while (len >= k) {
   
               for (int i=0; i<k; i++) {
   
                   next = curr.next;
                   curr.next = prev;
                   prev = curr;
                   curr = next;                
               }
   
               if (newHead == null) {
                   newHead = prev;
               }
   
               if (t1 != null) {
                   t1.next = prev;
               }
               t2.next = curr;
               t1 = t2;
               t2 = curr;
               prev = null;
               len = len-k;
   
           }
           return newHead;
       }

2. [HomeWork] 86. Partition List
   1. leetcode here

   public ListNode partition(ListNode head, int x) {
           
           ListNode lessHead = new ListNode(0);
           ListNode greaterHead = new ListNode(0);
           ListNode lessTail = lessHead;
           ListNode greateTail = greaterHead;
   
           while (head != null) {
               
               if (head.val < x) {
                   lessTail.next = head;
                   lessTail = head;
               } else {
                   greateTail.next = head;
                   greateTail = head;
               }
               head = head.next;
           }
   
           lessTail.next = greaterHead.next;
           greateTail.next = null;
           return lessHead.next;
       }

3. [HomeWork] 138. Copy List with Random Pointer
   1. leetcode here

   public Node copyRandomList(Node head) {
           
           if (head == null) {
               return null;
           }
   
           Node curr = head;
           while (curr != null) {
               Node newNode = new Node(curr.val);
               newNode.next = curr.next;
               curr.next = newNode;
               curr = newNode.next;
           }
           curr = head;
           while (curr != null) {
   
               curr.next.random = curr.random != null ? curr.random.next : null;
               curr = curr.next.next;
           }
   
           Node ptrOldList = head;
           Node ptrNewList = head.next;
           Node headOld = head.next;
   
           while (ptrOldList != null) {
   
               ptrOldList.next = ptrOldList.next.next;
               ptrNewList.next = (ptrNewList.next != null) ? ptrNewList.next.next : null;
               ptrOldList = ptrOldList.next;
               ptrNewList = ptrNewList.next;
           }
           return headOld;
       }

4. [HomeWork] 430. Flatten a Multilevel Doubly Linked List
   1. leetcode here

   public Node flatten(Node head) {
           
           if (head == null) {
               return null;
           }
           
           Node node = head;
           while (node != null) {
               if (node.child == null) {
                   node = node.next;
                   continue;
               }
   
               // Find tail to stitch to parents next -->
               Node tail = node.child;
               while (tail.next != null) {
                   tail = tail.next;
               }
               // <--
   
               // Stitch tail in next node -->
               tail.next = node.next;
               if (node.next != null) {
                   node.next.prev = tail;
               }
               // <--
               
               // Stitch current node to child nodes head -->
               node.next = node.child;
               node.child.prev = node;
               // <--
               
               // Unassign child node.
               node.child = null;
               
           }
   
           return head;
       }