🗓️ LeetCode Daily Challenge – Day 3

🔑 Prerequisite Knowledge:

Linked Lists – Key Points

1. Definition of Linked List:

   • A linked list is a linear data structure where each element, known as a node, contains two parts:
     • A data field to store the value.
     • A reference (or pointer) to the next node in the sequence.
   • The final node’s pointer refers to null, marking the end of the list.

2. Types of Linked Lists:

   • Singly Linked List: Nodes are linked sequentially, with each node pointing to the next one.
   • Doubly Linked List: Each node contains two pointers, one to the next node and one to the previous node, allowing traversal in both directions.
     
   • Circular Linked List: The last node links back to the first node, creating a loop structure. Suitable to solve the Josephus problem.

3. Linked List Memory Storage:

   • Array vs Linked List Memory Layout:
     • Arrays: Elements are stored in contiguous blocks of memory, making random access (e.g., arr[5]) efficient with $O(1)$ time complexity.
     • Linked Lists: Elements are scattered in non-contiguous memory and connected via pointers. Memory allocation happens dynamically, and the nodes are not stored in a continuous sequence.
       
   • In linked lists, each node points to the next node, which may be located anywhere in memory.
     • Pros: Flexible memory usage (no need to pre-allocate memory like arrays).
     • Cons: Slower access time due to the need to traverse nodes sequentially ($O(n)$ to find an element).

4. Node Definition in Code:

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

5. Advantages and Limitations:

   • Advantages:
     • Dynamic size: Linked lists can grow or shrink in size easily by adding/removing nodes.
     • Efficient insertions/deletions: Adding or removing elements (especially at the beginning or middle) is efficient ($O(1)$ for insert/delete). In arrays, these operations can require shifting elements, making them $O(n)$.
     • Delete node
     • Insert node
     • No pre-allocation: Memory is allocated as needed for each new node.
   • Limitations:
     • Sequential access: To access a particular element, you have to traverse the list from the head, making searching or accessing elements slower than arrays ($O(n)$).
     • Extra memory: Each node requires extra memory for the pointer/reference field, which increases the overhead compared to arrays.

6. Key Points:

   • Basic Structure:
     • Linked lists are a sequence of nodes where each node contains data and a reference (or pointer) to the next node.
     • A single linked list only points forward, while doubly linked lists allow navigation both forward and backward.
   • Memory Management:
     • Languages like C/C++ require explicit memory management (deleting nodes), while Python/Java have garbage collection to handle this.
     • Memory cleanup is essential in C++ to avoid memory leaks, even if not strictly necessary for LeetCode submissions.
   • Common Operations:
     • Operations like insertion, deletion, and traversal are typical, with time complexity depending on the position of nodes in the list.
     • Deleting a node requires updating pointers, especially handling the head separately for ease.
   • Dummy Node Technique:
     • A dummy node can simplify edge cases by ensuring there’s always a non-null previous node, even if the first node needs deletion.

🧠 LeetCode Problem 203: Remove Linked List Elements

🚀 A. Problem Description:

Given a linked list and a value val, remove all nodes from the list that have val as their value. Return the modified list. You can find the full problem description here. 👈
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]

Example 2:
Input: head = [], val = 1
Output: []

Example 3:
Input: head = [7,7,7,7], val = 7
Output: []

Constraints:

• The number of nodes in the list is in the range [0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• Node.val is an integer value in the range [-10⁵, 10⁵].

💡 B. Thought Process:

1. Understand the problem: 🤔

   • We need to delete nodes from a linked list that have a specified value, val.
   • The head itself may need deletion, and subsequent nodes should be reconnected to avoid broken references.

2. Break it down:

   • 📥 Inputs: Head of the linked list and an integer val.
   • 📤 Outputs: Modified linked list without nodes containing val.
   • 💭 Edge cases: Empty list, all nodes have val, or val doesn’t exist in the list.

3. Choose an approach:

   • Version 1: Delete nodes directly from the original list by handling the head separately.
   • Version 2: Use a dummy node, allowing a uniform deletion approach.
   • Version 3: Apply recursion to delete nodes in a backtracking manner.

🔨 C. Approach 1: Direct Deletion with Head Handling

📝 Plan:

1. Head Removal: Remove all leading nodes with val.
2. Iterate and Delete: Traverse the list, deleting nodes by updating pointers.
3. Return Modified List: Return the head of the modified list.

🧮 Complexity:

• ⏳ Time complexity: O(n)
• 🗂️ Space complexity: O(1)

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Remove nodes from the start of the list with the target value
        while head is not None and head.val == val:
            head = head.next  # Move head to the next node
        
        # Traverse through the list to delete nodes with the value `val`
        current = head
        while current is not None and current.next is not None:
            if current.next.val == val:
                # Skip over the node with value `val`
                current.next = current.next.next
            else:
                # Move to the next node
                current = current.next
        
        return head

🔨 C. Approach 2: Dummy Node Technique

📝 Plan:

1. Create Dummy Node: Attach a dummy node before the head to simplify handling the head case.
2. Traverse and Delete: Iterate through the list, deleting nodes with val using next pointers.
3. Return the Result: Return dummy_head.next to get the new head.

🧮 Complexity:

• ⏳ Time complexity: O(n)
• 🗂️ Space complexity: O(1)

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Create a dummy node to handle edge cases with the head
        dummy_head = ListNode(next=head)
        
        # Start traversing from the dummy node
        current = dummy_head
        while current.next is not None:
            if current.next.val == val:
                # Bypass the node with the value `val`
                current.next = current.next.next
            else:
                # Move to the next node
                current = current.next
        
        return dummy_head.next  # Return the actual head of the modified list

🔨 C. Approach 3: Recursive Solution

📝 Plan:

1. Base Case: If head is null, return null.
2. Recursive Case: If head->val equals val, delete the head and recurse on the next node.
3. Return: Concatenate results and return the modified head.

🧮 Complexity:

• ⏳ Time complexity: O(n)
• 🗂️ Space complexity: O(n) due to recursion stack

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        # Base case: empty list
        if head is None:
            return None
        
        # Recursively call removeElements on the next node
        head.next = self.removeElements(head.next, val)
        
        # If the current head's value is `val`, skip it by returning head.next
        return head.next if head.val == val else head

🔎 D. Edge Cases:

• Empty List: The list is empty initially.
• All Nodes Have val: Every node should be deleted.
• val Not Found: The list remains unchanged.

🔗 E. Similar Questions:

• 🔗 21. Merge Two Sorted Lists
• 🔗 237. Delete Node in a Linked List
• 🔗 83. Remove Duplicates from Sorted List

🧠 LeetCode Problem 707: Design Linked List

🚀 A. Problem Description

Design a singly or doubly linked list class, MyLinkedList, with the following operations:

• get(index): Returns the value at index, or -1 if index is invalid.
• addAtHead(val): Adds a node with val at the head.
• addAtTail(val): Appends a node with val at the tail.
• addAtIndex(index, val): Inserts val at index, adjusting node links accordingly.
• deleteAtIndex(index): Deletes the node at index if it exists.

Example 1:

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]

Output:
[null, null, null, null, 2, null, 3]

Constraints:

• 0 <= index, val <= 10^4
• Methods will be called up to 2000 times.

💡 B. Thought Process:

1. Understand the requirements: Implement five linked list functions.
2. Handle edge cases:
   • index is out of bounds.
   • Head or tail modifications.
3. Choose an approach:
   • Single-linked list: Simple and space-efficient.
   • Double-linked list: Easier for bidirectional access and middle insertions.

🔨 C. Approach 1: Singly Linked List

📝 Plan:

1. Define Node and MyLinkedList classes.
2. Implement functions:
   • get: Traverse to find the node at index.
   • addAtHead, addAtTail: Adjust pointers for new head or tail nodes.
   • addAtIndex: Traverse to index-1 and insert.
   • deleteAtIndex: Traverse to index-1 and delete.

🧮 Complexity:

• ⏳ Time complexity: O(index) for functions involving traversal.
• 🗂️ Space complexity: O(n) for linked list size.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        # Initialize dummy head and size counter
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        
        current = self.dummy_head.next  # Start from the head
        for i in range(index):
            current = current.next
        
        return current.val if current else -1

    def addAtHead(self, val: int) -> None:
        # Insert new node at the beginning (head)
        new_node = ListNode(val, self.dummy_head.next)
        self.dummy_head.next = new_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        # Traverse to the end and append new node
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        
        current = self.dummy_head
        for i in range(index):  # Stop one before the insertion index
            current = current.next
        new_node = ListNode(val, current.next)
        current.next = new_node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        
        current = self.dummy_head
        for i in range(index):  # Stop one before the deletion index
            current = current.next
        current.next = current.next.next  # Remove node
        self.size -= 1

🔨 C. Approach 2: Doubly Linked List

📝 Plan:

1. Add Previous Pointer: Each node has both next and prev pointers.
2. Traverse from Head or Tail:
   • Use head for indices closer to 0 and tail for indices closer to size-1.
3. Bidirectional Insertion/Deletion:
   • Adjust prev and next pointers for better efficiency.

🧮 Complexity:

• ⏳ Time complexity: O(min(index, size-index)) for functions needing traversal.
• 🗂️ Space complexity: O(n) for linked list size.

class ListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

class MyLinkedList:
    def __init__(self):
        # Initialize head and tail pointers and size counter
        self.head = None
        self.tail = None
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        
        # Optimize traversal direction
        if index < self.size // 2:
            current = self.head
            for i in range(index):
                current = current.next
        else:
            current = self.tail
            for i in range(self.size - index - 1):
                current = current.prev
        
        return current.val

    def addAtHead(self, val: int) -> None:
        new_node = ListNode(val, None, self.head)
        if self.head:
            self.head.prev = new_node
        else:
            self.tail = new_node
        self.head = new_node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        new_node = ListNode(val, self.tail, None)
        if self.tail:
            self.tail.next = new_node
        else:
            self.head = new_node
        self.tail = new_node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return
        if index == 0:
            self.addAtHead(val)
        elif index == self.size:
            self.addAtTail(val)
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index - 1):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index):
                    current = current.prev
            new_node = ListNode(val, current, current.next)
            current.next.prev = new_node
            current.next = new_node
            self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        if index == 0:
            self.head = self.head.next
            if self.head:
                self.head.prev = None
            else:
                self.tail = None
        elif index == self.size - 1:
            self.tail = self.tail.prev
            if self.tail:
                self.tail.next = None
            else:
                self.head = None
        else:
            if index < self.size // 2:
                current = self.head
                for i in range(index):
                    current = current.next
            else:
                current = self.tail
                for i in range(self.size - index - 1):
                    current = current.prev
            current.prev.next = current.next
            current.next.prev = current.prev
        self.size -= 1

🔎 D. Edge Cases:

• Empty List: All operations should handle the empty state gracefully.
• Out of Bounds: Ensure index checks are correct.
• Head/Tail Modifications: Insertions or deletions at head/tail need pointer adjustments.

🔗 E. Similar Questions:

• 🔗 21. Merge Two Sorted Lists
• 🔗 146. LRU Cache
• 🔗 83. Remove Duplicates from Sorted List

🧠 LeetCode Problem 206: Reverse Linked List

🚀 A. Problem Description

Given the head of a singly linked list, reverse the list and return the reversed list’s head.

Example 1:

• Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
• Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Constraints:

• The number of nodes in the list is in the range [0, 5000].
• -5000 <= Node.val <= 5000

💡 B. Thought Process

1. Understand the Problem:

   • The goal is to reverse the pointers in a linked list so that each node’s next pointer points to the previous node instead of the next one.
   • The two main approaches for this are the iterative approach using two pointers and the recursive approach, which is slightly more complex but achieves the same result.

2. Break It Down:

   • 📥 Inputs: The head node of a singly linked list.
   • 📤 Outputs: The head of the reversed list.
   • 💭 Edge Cases:
     • Empty list (head = NULL).
     • List with only one node (reversing has no effect).
     • Long lists where recursive approaches may hit stack limitations.

3. Choose an Approach:

   • Iterative Approach: Uses two pointers (prev and current) to reverse the next pointers iteratively.
   • Recursive Approach: Uses the call stack to reverse the pointers, effectively treating each call as a new frame for each node’s reversal.

🔨 C. Approach 1: Iterative (Two Pointers)

📝 Plan

The iterative approach efficiently reverses the list with a time complexity of O(n) and space complexity of O(1).

1. Initialize two pointers: prev (set to None) and current (set to the head).
2. Loop through the list, adjusting pointers:
   • Save the next node (temp = current.next).
   • Reverse the next pointer of current to point to prev.
   • Move prev and current one step forward.
3. After the loop, prev will be the new head of the reversed list.

🧮 Complexity

• ⏳ Time complexity: O(n) since each node is visited once.
• 🗂️ Space complexity: O(1) because no additional space is needed apart from a few pointers.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        while current:
            temp = current.next  # Store next node
            current.next = prev  # Reverse current node's pointer
            prev = current       # Move prev to current
            current = temp       # Move current to next node
        return prev

🔨 C. Approach 2: Recursive

📝 Plan

The recursive approach leverages the call stack to reverse the list.

1. Define a helper function that takes prev and current as arguments.
2. For each recursive call:
   • If current is None, return prev (new head of reversed list).
   • Otherwise, store current.next in temp, reverse the pointer by setting current.next = prev, and call the function recursively with temp and current.
3. The last node will eventually point back to the previous node in each recursive call, effectively reversing the list.

🧮 Complexity

• ⏳ Time complexity: O(n) due to the recursion through each node.
• 🗂️ Space complexity: O(n) since each call adds a frame to the call stack.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        def reverse(prev, current):
            if not current:
                return prev
            temp = current.next
            current.next = prev
            return reverse(current, temp)
        return reverse(None, head)

🔨 C. Approach 3: Recursive (Back to Front)

📝 Plan

This approach starts the reversal process from the end of the list:

1. Base Cases:
   • If head is None (empty list) or head.next is None (single node list), we return head because no reversal is needed.
2. Recursive Call:
   • Recursively call reverseList on head.next to reverse the rest of the list from the second node onward.
   • When the recursion unwinds, each node points back to its previous node, effectively reversing the list.
3. Reverse Pointers:
   • Set head.next.next to head to reverse the pointer direction.
   • Finally, set head.next to None so the original head becomes the new tail of the reversed list.
4. Return:
   • Return the last pointer, which becomes the new head after the full reversal.

🧮 Complexity

• ⏳ Time complexity: O(n) as each node is processed once.
• 🗂️ Space complexity: O(n) due to recursive call stack usage for n nodes.

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # Base case: If list is empty or has a single node
        if head is None or head.next is None:
            return head

        # Recursive call to reverse the rest of the list
        last = self.reverseList(head.next)

        # Reverse the pointers
        head.next.next = head  # Set the next node's next pointer back to current head
        head.next = None       # Set the current head's next pointer to None to form the new tail

        return last  # Last becomes the new head of the reversed list

🔎 D. Edge Cases

• Empty list: head = None should return None.
• Single node: head with one node should return the same node.
• Long list: Ensure that the recursive method handles long lists within stack limits.

🔗 E. Similar Questions

• 🔗 Reverse Nodes in k-Group
• 🔗 Palindrome Linked List
• 🔗 Swap Nodes in Pairs
• 🔗 Linked List Cycle