🗓️ LeetCode Daily Challenge – Day 4

🧠 LeetCode Problem 24: Swap Nodes in Pairs

🚀 A. Problem Description:

You are given a linked list, and you need to swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the nodes (only nodes themselves may be changed).

Example 1:
Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation: The nodes 1 and 2 are swapped, and then nodes 3 and 4 are swapped.

Example 2:
Input: head = []
Output: []
Explanation: The list is empty, so nothing changes.

Example 3:
Input: head = [1]
Output: [1]
Explanation: There’s only one node, so no swaps occur.

Constraints:

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

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔

   • The task involves swapping adjacent nodes in a linked list while maintaining the connections properly.
   • This requires pointer manipulation, making it crucial to be cautious about the order of operations.
   • Special cases include an empty list or a list with only one node.

2. Break it down:

   • 📥 Inputs: A singly linked list head.
   • 📤 Outputs: A singly linked list with swapped adjacent nodes.
   • 💭 Edge cases: An empty list (head = None), a single-node list (head.next = None), and lists with odd numbers of nodes.

3. Choose an approach:

   • Version 1: Use recursion to handle node swaps.
   • Version 2: Use a dummy head and iterative pointer manipulation.
   • Version 3: Iterative approach without a dummy head for simplicity.

🔨 C. Approach 1: Recursion

📝 Plan:

1. If the list has fewer than two nodes, return the head as-is.
2. Swap the first two nodes and recursively call the function for the rest of the list.
3. Return the new head of the list after swapping.

🧮 Complexity:

• ⏳ Time complexity: O(n), where n is the number of nodes in the list.
• 🗂️ Space complexity: O(n), due to the recursion stack.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:  # Base case
            return head
        
        # Nodes to be swapped
        first_node = head
        second_node = head.next
        
        # Recursively swap the remaining pairs
        first_node.next = self.swapPairs(second_node.next)
        second_node.next = first_node
        
        # Return the new head
        return second_node

🔨 C. Approach 2: Dummy Head Approach

📝 Plan:

1. Create a dummy head pointing to the original list to simplify pointer manipulation.
2. Use a current pointer starting at the dummy head to traverse the list in pairs.
3. Swap the nodes by updating their next pointers.
4. Move the pointer to the next pair and repeat until the end of the list.

🧮 Complexity:

• ⏳ Time complexity: O(n), as we traverse the entire list.
• 🗂️ Space complexity: O(1), since no additional space is used apart from pointers.

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        dummy = ListNode(-1)
        dummy.next = head
        current = dummy
        
        while current.next and current.next.next:
            # Identify the nodes to be swapped
            first_node = current.next
            second_node = current.next.next
            
            # Perform the swap
            first_node.next = second_node.next
            second_node.next = first_node
            current.next = second_node
            
            # Move the pointer to the next pair
            current = first_node
        
        return dummy.next

🔨 C. Approach 3: Without Dummy Head

📝 Plan:

1. Handle the edge cases of an empty list or a single-node list upfront.
2. Swap the first pair manually to set the new head of the list.
3. Traverse the list iteratively, swapping pairs by updating pointers.

🧮 Complexity:

• ⏳ Time complexity: O(n), as we traverse the entire list.
• 🗂️ Space complexity: O(1), since no recursion or additional data structures are used.

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if not head or not head.next:  # Edge cases
            return head
        
        # Update the head to the second node
        new_head = head.next
        
        prev = None
        current = head
        
        while current and current.next:
            # Nodes to be swapped
            first_node = current
            second_node = current.next
            
            # Swap the nodes
            first_node.next = second_node.next
            second_node.next = first_node
            
            # Connect the previous pair to the current swapped pair
            if prev:
                prev.next = second_node
            
            # Update pointers for the next iteration
            prev = first_node
            current = first_node.next
        
        return new_head

🔎 D. Edge Cases:

• Empty list: The input list is None, and the output should also be None.
• Single-node list: The input list has only one node, so no swaps occur.
• Odd number of nodes: The last node remains in its original position.

🔗 E. Similar Questions:

• 🔗 Reverse Nodes in k-Group
• 🔗 Rotate List
• 🔗 Reverse Linked List

🧠 LeetCode Problem 19: Remove Nth Node From End of List

🚀 A. Problem Description:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: The second node from the end is 4, which is removed.

Example 2:
Input: head = [1], n = 1
Output: []
Explanation: The only node is removed, leaving the list empty.

Example 3:
Input: head = [1,2], n = 1
Output: [1]
Explanation: The last node (2) is removed.

Constraints:

• The number of nodes in the list is in the range [1, 30].
• 0 <= Node.val <= 100
• 1 <= n <= sz, where sz is the size of the list.

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔

   • The task is to remove the nth node from the end of a linked list.
   • This requires efficiently identifying the target node while maintaining pointer connections.
   • Special cases include removing the first node (when n equals the size of the list) or when the list contains only one node.

2. Break it down:

   • 📥 Inputs: A singly linked list head and an integer n.
   • 📤 Outputs: A singly linked list with the nth node from the end removed.
   • 💭 Edge cases: Single-node list (n = 1), removing the head node (n = size of list), or lists with two nodes.

3. Choose an approach:

   • Version 1: Traverse the list twice (once to calculate the size, then to remove the node).
   • Version 2: Use two pointers (fast and slow) to locate the node in one pass.
   • Version 3: Recursion-based solution to count nodes from the end.

🔨 C. Approach 1: Two Traversals

📝 Plan:

1. Traverse the entire list to calculate its length.
2. Identify the position of the target node to remove (length - n).
3. Traverse the list a second time to remove the node.

🧮 Complexity:

• ⏳ Time complexity: O(n), where n is the number of nodes in the list (two traversals).
• 🗂️ Space complexity: O(1), as no extra space is used.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def get_length(node):
            length = 0
            while node:
                length += 1
                node = node.next
            return length
        
        length = get_length(head)
        dummy = ListNode(0, head)
        current = dummy
        
        # Traverse to the node before the target node
        for _ in range(length - n):
            current = current.next
        
        # Remove the target node
        current.next = current.next.next
        
        return dummy.next

🔨 C. Approach 2: Two-Pointer Technique

📝 Plan:

1. Use a dummy head to simplify pointer manipulation.
2. Initialize two pointers, fast and slow, both pointing to the dummy head.
3. Move fast pointer n + 1 steps ahead.
4. Move both fast and slow simultaneously until fast reaches the end of the list.
5. Remove the node after slow.

🧮 Complexity:

• ⏳ Time complexity: O(n), as we traverse the list once.
• 🗂️ Space complexity: O(1).

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        fast, slow = dummy, dummy
        
        # Move fast pointer n+1 steps ahead
        for _ in range(n + 1):
            fast = fast.next
        
        # Move both pointers until fast reaches the end
        while fast:
            fast = fast.next
            slow = slow.next
        
        # Remove the nth node
        slow.next = slow.next.next
        
        return dummy.next

🔨 C. Approach 3: Recursion

📝 Plan:

1. Use recursion to traverse to the end of the list while maintaining a counter.
2. Increment the counter on the way back to identify the target node.
3. Remove the node when the counter matches n + 1 (the node before the target).

🧮 Complexity:

• ⏳ Time complexity: O(n), as we traverse the list once.
• 🗂️ Space complexity: O(n), due to the recursion stack.

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0, head)
        self.counter = 0
        
        def recurse(node):
            if not node:
                return
            recurse(node.next)
            self.counter += 1
            if self.counter == n + 1:
                node.next = node.next.next
        
        recurse(dummy)
        return dummy.next

🔎 D. Edge Cases:

• Single-node list: The input is [1] with n = 1, and the output should be an empty list ([]).
• Remove the head node: For a list [1, 2, 3] with n = 3, the output should be [2, 3].
• Short lists: For a list [1, 2] with n = 1, the output should be [1].

🔗 E. Similar Questions:

• 🔗 Reverse Linked List
• 🔗 Remove Duplicates from Sorted List
• 🔗 Merge Two Sorted Lists

Here’s a blog post for LeetCode Problem 02.07: Intersection of Two Linked Lists, with two approaches.

🧠 LeetCode Problem 02.07: Intersection of Two Linked Lists

🚀 A. Problem Description:

Write a program to find the node at which two singly linked lists intersect. If the two linked lists have no intersection, return None.

You must solve the problem in O(n) time complexity and use only O(1) additional memory.

Example 1:
Input:
headA = [4,1,8,4,5]
headB = [5,6,1,8,4,5]
Output: Intersection node with value 8.

Example 2:
Input:
headA = [2,6,4]
headB = [1,5]
Output: None (No intersection).

Constraints:

• The number of nodes in both lists is in the range [0, 3 * 10⁴].
• The values of the nodes are between -10000 and 10000.
• Both lists may intersect at most one node.

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔

   • The goal is to find the intersection node where two linked lists converge.
   • Intersection means pointer equality, not just value equality.
   • If no intersection exists, the output should be None.

2. Break it down:

   • 📥 Inputs: Two singly linked lists headA and headB.
   • 📤 Outputs: The node at which the two lists intersect, or None if no intersection exists.
   • 💭 Edge cases: One or both lists are empty; no intersection exists; the lists intersect at the head node.

3. Choose an approach:

   • Approach 1: Calculate the lengths of the two lists, align them, and traverse simultaneously to find the intersection.
   • Approach 2: Use two pointers and switch heads to equalize traversal distances.

🔨 C. Approach 1: Calculate Lengths and Align

📝 Plan:

1. Calculate the lengths of both linked lists.
2. Compute the difference in lengths (d).
3. Move the longer list’s pointer d steps forward to align both lists’ end positions.
4. Traverse both lists simultaneously to check for intersection.
5. Return the intersection node if found, otherwise return None.

🧮 Complexity:

• ⏳ Time complexity: O(n + m), where n and m are the lengths of the two lists.
• 🗂️ Space complexity: O(1).

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        def getLength(head):
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        # Get lengths of both lists
        lenA = getLength(headA)
        lenB = getLength(headB)
        
        # Align the lists
        if lenA > lenB:
            for _ in range(lenA - lenB):
                headA = headA.next
        else:
            for _ in range(lenB - lenA):
                headB = headB.next
        
        # Traverse both lists to find the intersection
        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        
        return None

🔨 C. Approach 2: Two-Pointer Technique

📝 Plan:

1. Use two pointers, pointerA and pointerB, starting at the heads of the two lists.
2. Traverse both lists. If a pointer reaches the end of its list, switch it to the other list’s head.
3. Continue until the two pointers meet at the intersection node or both reach None.
4. Return the intersection node if they meet, otherwise return None.

🧮 Complexity:

• ⏳ Time complexity: O(n + m), where n and m are the lengths of the two lists.
• 🗂️ Space complexity: O(1).

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        pointerA, pointerB = headA, headB
        
        # Traverse both lists until pointers meet or both are None
        while pointerA != pointerB:
            pointerA = pointerA.next if pointerA else headB
            pointerB = pointerB.next if pointerB else headA
        
        return pointerA

🔎 D. Edge Cases:

• Empty lists: If headA or headB is None, return None.
• No intersection: The lists do not intersect, so the output is None.
• Immediate intersection: The lists intersect at the very first node.

🔗 E. Similar Questions:

• 🔗 Linked List Cycle
• 🔗 Reverse Linked List
• 🔗 Merge Two Sorted Lists

🧠 LeetCode Problem 142: Linked List Cycle II

🚀 A. Problem Description:

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return None.

To represent a cycle in the given linked list, the position of the node is connected to another node. A cycle starts from that position.

You must solve the problem using O(n) time complexity and O(1) space complexity.

Example 1:
Input: head = [3,2,0,-4], where pos = 1 (cycle at node 2).
Output: The node with value 2.

Example 2:
Input: head = [1,2], where pos = 0 (cycle at node 1).
Output: The node with value 1.

Example 3:
Input: head = [1], where pos = -1 (no cycle).
Output: None.

Constraints:

• The number of nodes in the list is in the range [0, 10⁴].
• -10⁵ <= Node.val <= 10⁵
• pos is -1 or a valid index in the linked list.

You can find the full problem description here. 👈

💡 B. Thought Process:

1. Understand the problem: 🤔

   • First, detect whether the linked list has a cycle.
   • If a cycle exists, return the node where the cycle begins.
   • If there is no cycle, return None.

2. Break it down:

   • 📥 Inputs: A singly linked list head.
   • 📤 Outputs: The node where the cycle begins or None.
   • 💭 Edge cases: No cycle; cycle at the head node; single-node list with or without a cycle.

3. Choose an approach:

   • Approach 1: Use the two-pointer technique (fast and slow pointers).
   • Approach 2: Use a hash set to detect visited nodes.

🔨 C. Approach 1: Two-Pointer Technique

📝 Plan:

1. Use two pointers, fast and slow.
   • fast moves two steps at a time.
   • slow moves one step at a time.
2. If there’s a cycle, the two pointers will eventually meet inside the cycle.
3. To find the cycle’s entry point:
   • Move one pointer back to the head.
   • Move both pointers one step at a time until they meet.
   • The meeting point is the cycle’s entry point.

🧮 Complexity:

• ⏳ Time complexity: O(n), where n is the number of nodes in the linked list.
• 🗂️ Space complexity: O(1), as no extra space is used.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            # If there is a cycle, the slow and fast pointers will eventually meet
            if slow == fast:
                # Move one of the pointers back to the start of the list
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow  # The cycle entry point
        # If there is no cycle, return None
        return None

🔨 C. Approach 2: Hash Set

📝 Plan:

1. Use a hash set to store visited nodes.
2. Traverse the linked list node by node.
   • If a node is already in the hash set, it’s the start of the cycle.
   • Otherwise, add the node to the hash set.
3. If the end of the list is reached, there’s no cycle.

🧮 Complexity:

• ⏳ Time complexity: O(n), where n is the number of nodes in the linked list.
• 🗂️ Space complexity: O(n), due to the hash set storing visited nodes.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        visited = set()
        
        while head:
            if head in visited:
                return head  # Cycle entry point
            visited.add(head)
            head = head.next
        
        return None  # No cycle

🔎 D. Edge Cases:

• No cycle: A linked list without a cycle should return None.
• Single-node list: If the list has only one node:
  • With pos = -1, there’s no cycle.
  • With pos = 0, the node points to itself, forming a cycle.
• Cycle at the head: The first node itself forms the start of the cycle.

🔗 E. Similar Questions:

• 🔗 Linked List Cycle
• 🔗 Intersection of Two Linked Lists
• 🔗 Reverse Linked List