Session 23: Linked List 2

Original Session

Date: 28 Dec 2024

Topic: Linked List 2

Concept: Always create dummy in case of LinledList, so you dont loose head.

Programs

1. 21. Merge Two Sorted Lists
   1. Without creating extra linkedlist.
   2. leetcode here

   public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
           
           ListNode temp = new ListNode(0);
           ListNode res = temp;
       
           while (list1 != null && list2 != null) {
                   
                   if (list1.val < list2.val) {
   
                       temp.next = list1;
                       list1 = list1.next;
                       temp = temp.next;
                   } else {
   
                       temp.next = list2;
                       list2 = list2.next;
                       temp = temp.next;
                   }
           }
   
           if (list1 != null) {
   
               temp.next = list1;
           }
   
           if (list2 != null) {
   
               temp.next = list2;
           }
   
           return res.next;
       }

2. 23. Merge k Sorted Lists
   1. leetcode here

   public ListNode mergeKLists(ListNode[] lists) {
           
           if (lists.length == 0) {
               return null;
           }
   
           if (lists.length == 1) {
               return lists[0];
           }
   
           ListNode merged = mergeTwoLists(lists[0], lists[1]);
   
           for (int i = 2; i < lists.length; i++) {
   
               merged = mergeTwoLists(merged, lists[i]);
           }
   
           return merged;
       }
   
       ListNode mergeTwoLists(ListNode list1, ListNode list2) {
           
           ListNode temp = new ListNode(0);
           ListNode res = temp;
       
           while (list1 != null && list2 != null) {
                   
                   if (list1.val < list2.val) {
   
                       temp.next = list1;
                       list1 = list1.next;
                       temp = temp.next;
                   } else {
   
                       temp.next = list2;
                       list2 = list2.next;
                       temp = temp.next;
                   }
           }
   
           if (list1 != null) {
   
               temp.next = list1;
           }
   
           if (list2 != null) {
   
               temp.next = list2;
           }
   
           return res.next;
       }

3. 61. Rotate List
   1. Altenative approach

      public ListNode rotateRight(ListNode head, int k) {
              
              if (head == null || head.next == null || k == 0) {
                  return head;
              }
      
              
              ListNode curr = head;
              int len = 1;
              while (curr.next != null) {
                  len ++;
                  curr = curr.next;
              }
      
              k = len - (k%len);
              curr.next = head;
      
              while (k>0) {
                  curr = curr.next;
                  k--;
              }
      
              head = curr.next;
              curr.next = null;
      
              return head;
          }

   2. leetcode here

   // Sliding window approach, similar to remove kth element from last.
   public ListNode rotateRight(ListNode head, int k) {
           
           if (head == null || head.next == null || k == 0) {
               return head;
           }
   
           
           ListNode dummy = new ListNode(0, head);
           ListNode right = dummy;
           int len = 0;
           while (right.next != null) {
               len ++;
               right = right.next;
           }
   
           right = dummy;
           ListNode temp = dummy;
   
           k = k%len;
           while (k > 0) {
               k--;
               right = right.next;
           }
   
           while (right.next != null) {
   
               temp = temp.next;
               right = right.next;
           }
   
           right.next = head;
           head = temp.next;
           temp.next = null;
   
           return head;
       }

4. 206. Reverse Linked List
   1. leetcode here

   public ListNode reverseList(ListNode head) {
           
           if (head == null) {
               return null;
           }
   
           ListNode prev = null;
           ListNode next = null;
           while(head != null) {
               
               next = head.next;
               head.next = prev;
   
               prev = head;
               head = next;
           }
           return prev;
       }