Session 21: Linked List

Original Session

Date: 22 Dec 2024

Topic: Linked List

Concept: Linked-List is linear data structure, but memory allocated is not linear.

Concept: while (curr ≠ null) {} will reach us to null after last node.

Concept: while (curr.next ≠ null) {} will reach us to last node.

Concept: Fast and Slow Pointers.

Concept: Count length of loop, once slow and fast meet, hold fast on same position and move slow until it reaches fast and count each time.

Concept: Head and “Slow + Fast” overlap, both are equal distance from node of beginning of loop.

Concept: In case of Intersection List, both heads traveling one node at a time and when reached to the end, point to opposite head. This will make both heads reach equal distance from intersection. If both head reach to null simultaneously we conclude no intersection.

Programs

  1. Count Linked List Nodes
    1. GFG here
    public int getCount(Node head) {
        // code here
        
        int count = 0;
        Node curr = head;
        
        while (curr != null) {
            
            count ++;
            curr = curr.next;
        }
        
        return count;
    }

  1. 876. Middle of the Linked List
    1. leetcode here
    public ListNode middleNode(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;
        }

        return slow;
    }

  1. 141. Linked List Cycle
    1. leetcode here
    public boolean hasCycle(ListNode head) {

        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

  1. Find length of Loop
    1. GFG here
    public int countNodesinLoop(Node head) {
        // Add your code here.
        
        Node slow = head;
        Node fast = head;
        int count = 0;
        
        // Find circular meet.
        while (fast != null && fast.next != null) {
            
            slow = slow.next;
            fast = fast.next.next;
            
            // From this meet move slow pointer for one loop.
            if (slow == fast) {
                count = 1;
                slow = slow.next;
                while (slow != fast) {
                  count ++;
                  slow = slow.next;
                }
                break;
            }
        }
        return count;
    }

  1. 142. Linked List Cycle II
    1. leetcode here
    public ListNode detectCycle(ListNode head) {
        
        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {

                ListNode curr = head;
                while (curr != slow) {
                    curr = curr.next;
                    slow = slow.next;
                }
                return curr;
            }
        }
        return null;
    }

  1. 160. Intersection of Two Linked Lists
    1. leetcode here
    1. Back to Head approach
      1. When list reaches end, point to opposite head. If both reach to null at same time, then not intersected. When both matches then intersected node reached.
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        ListNode currA = headA;
        ListNode currB = headB;

        while (currA != currB) {

            currA = currA.next;
            currB = currB.next;
            
            if (currA == null && currB == null) {
                return null;
            }

            if (currA == null) {
                currA = headB;
            }

            if (currB == null) {
                currB = headA;
            }
        }

        if (currA == currB) {
            return currA;
        }

        return null;
    }
    1. Skip first count elements approach
      1. Count distance pathA and pathB. skip number of elements from opposite path which is greater.
      public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        int distanceListA = 0;
        int distanceListB = 0;
        ListNode currA = headA;
        ListNode currB = headB;

        while (currA != null) {
            currA = currA.next;
            distanceListA ++;
        }

        while (currB != null) {
            currB = currB.next;
            distanceListB ++;
        }

        int skipA = 0, skipB = 0;
        if ((distanceListA - distanceListB) > 0) {

            skipA = distanceListA - distanceListB;
        } else if ((distanceListB - distanceListA) > 0) {

            skipB = distanceListB - distanceListA;
        }

        while (skipA > 0) {
            headA = headA.next;
            skipA --;
        }

        while (skipB > 0) {
            headB = headB.next;
            skipB --;
        }

        while (headA != headB && headA != null && headB != null) {
            headA = headA.next;
            headB = headB.next;
        }
        
        if (headA == headB) {
            return headA;
        }

        return null;
    }

  1. [Home Work] 19. Remove Nth Node From End of List
    1. leetcode here
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy;
        ListNode windowLeft = head;
        ListNode windowRight = dummy;

        while (n > 0) {

            windowRight = windowRight.next;
            n--;
        }

        while (windowRight.next != null) {

            windowRight = windowRight.next;
            windowLeft = windowLeft.next;
            prev = prev.next;
        }

        prev.next = windowLeft.next;

        return dummy.next;
    }

  1. [Home Work] 2. Add Two Numbers
    1. leetcode here
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
        int sum = 0;
        int carry = 0;
        ListNode dummy = new ListNode(0);
        ListNode pointer = dummy;

        // condition of carry added for case in which last number addition leads to carry.
        while (l1 != null || l2 != null || carry > 0) {
            
            sum += carry;
            if (l1 != null) {
                
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum/10;
            sum = sum%10;

            ListNode node = new ListNode(sum);
            pointer.next = node;
            pointer = node;

            sum = 0;
        } 
        return dummy.next;
    }