07. Linked List

Problems at a glance

LC	Problem
876	Middle of the Linked List	↗
141	Linked List Cycle	↗
142	Linked List Cycle II	↗
234	Palindrome Linked List	↗
206	Reverse Linked List	↗
92	Reverse Linked List II	↗
25	Reverse Nodes in k-Group	↗
143	Reorder List	↗
61	Rotate List	↗
19	Remove N-th Node From End of List	↗
237	Delete Node in a Linked List	↗
203	Remove Linked List Elements	↗
328	Odd Even Linked List	↗
21	Merge Two Sorted Lists (Recursive)	↗
138	Copy List with Random Pointer	↗
430	Flatten a Multilevel Doubly Linked List	↗
445	Add Two Numbers II	↗
23	Merge k Sorted Lists	↗
2	Add Two Numbers	↗
1669	Merge in Between Linked Lists	↗
2181	Merge Nodes in Between Zeros	↗
24	Swap Nodes in Pairs	↗
1721	Swapping Nodes in a Linked List	↗
86	Partition List	↗

---

1. Two‑Pointer (Fast & Slow Pointers)

Problem 1: Middle of the Linked List (Leetcode:876)

Problem Statement

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

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

Code and Explanation

Approach 1 — Fast & Slow PointersApproach 2 — Two-Pass Count

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Explanation:

1. Initialize: Set slow and fast both to head.
2. Move at different speeds: Advance slow one step and fast two steps per iteration.
3. Stop at end: When fast can no longer move (None or fast.next is None), slow sits at the middle.
4. Even length: Because fast stops on the last node (not past it), the second middle is returned for even-length lists.

Time: O(n)  |  Space: O(1)

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        for _ in range(length // 2):
            head = head.next
        return head

Explanation:

1. Count nodes: Walk the list once to get length.
2. Walk to middle: Advance head by length // 2 steps.
3. Return: The node at that position is the middle (second middle when length is even).

Time: O(n)  |  Space: O(1) — two passes but still constant space.

Problem 2: Linked List Cycle (Leetcode:141)

Problem Statement

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

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

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation

Approach 1 — Floyd's Cycle DetectionApproach 2 — Hash Set

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

Explanation:

1. Two pointers: slow moves 1 step, fast moves 2 steps.
2. Cycle check: If they meet inside the loop, a cycle exists.
3. No cycle: If fast reaches None, the list is acyclic.

Time: O(n)  |  Space: O(1)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        while head:
            if head in seen:
                return True
            seen.add(head)
            head = head.next
        return False

Explanation:

1. Track visited nodes: Add each node to a set while walking the list.
2. Detect repeat: Revisiting a node means there is a cycle.
3. End of list: Reaching None means no cycle.

Time: O(n)  |  Space: O(n)

Problem 3: Linked List Cycle II(Leetcode:142)

Problem Statement

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

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

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Code and Explanation

Approach 1 — Floyd's + Reset PointerApproach 2 — Hash Set

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        else:
            return None
        slow = head
        while slow != fast:
            slow = slow.next
            fast = fast.next
        return slow

Explanation:

1. Phase 1 — detect cycle: Move slow 1 step and fast 2 steps until they meet (or fast ends).
2. No cycle: If the loop exits via else (no meeting), return None.
3. Phase 2 — find entrance: Reset slow to head. Move both pointers 1 step at a time until they meet again — that node is the cycle start.
4. Math insight: Distance from head to cycle start equals distance from meeting point to cycle start (measured inside the loop).

Time: O(n)  |  Space: O(1)

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        while head:
            if head in seen:
                return head
            seen.add(head)
            head = head.next
        return None

Explanation:

1. Walk and record: Store every visited node in a hash set.
2. First repeat: The first node seen twice is where the cycle begins.
3. No cycle: Return None if the list ends.

Time: O(n)  |  Space: O(n)

Problem 4: Palindrome Linked List(Leetcode:234)

Problem Statement

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

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

Follow up: Could you do it in O(n) time and O(1) space?

Code and Explanation

Approach 1 — Find Middle + Reverse + CompareApproach 2 — Array Buffer

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        prev = None
        while slow:
            nxt = slow.next
            slow.next = prev
            prev = slow
            slow = nxt

        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Explanation:

1. Find middle: Use fast/slow pointers so slow ends at the second half's start.
2. Reverse second half: In-place reversal from slow; prev becomes the tail of the first half / head of reversed second half.
3. Compare halves: Walk left from head and right from prev simultaneously.
4. Mismatch: Any unequal values → not a palindrome.

Time: O(n)  |  Space: O(1)

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        return vals == vals[::-1]

Explanation:

1. Copy values: Store all node values in an array.
2. Check palindrome: Compare the array with its reverse.
3. Trade-off: Simple and readable, but uses O(n) extra space.

Time: O(n)  |  Space: O(n)

2. Reversal of Linked List

Problem 1: Reverse Linked List (Leetcode:206)

Problem Statement

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Code and Explanation

Approach 1 — IterativeApproach 2 — Recursive

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt
        return prev

Explanation:

1. Three pointers: prev (reversed portion), head (current), nxt (saved next).
2. Flip link: Point head.next to prev, then advance all three pointers.
3. Return: prev is the new head when head becomes None.

Time: O(n)  |  Space: O(1)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Explanation:

1. Base case: Empty or single-node list is already reversed.
2. Recurse: Reverse everything after head; new_head is the tail of the original list.
3. Rewire: Make the next node point back to head, then sever head.next.

Time: O(n)  |  Space: O(n) call stack

Problem 2: Reverse Linked List II (Leetcode:92)

Problem Statement

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?

Code and Explanation

Approach 1 — Dummy Head + In-Place Reverse SegmentApproach 2 — Extract + Reverse + Reconnect

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        curr = prev.next
        for _ in range(right - left):
            nxt = curr.next
            curr.next = nxt.next
            nxt.next = prev.next
            prev.next = nxt
        return dummy.next

Explanation:

1. Dummy head: Simplifies reversal when left == 1.
2. Walk to left - 1: prev anchors the node just before the sublist.
3. Repeated head-insert: For each node in the range, pull the next node to the front of the sublist (like reversing k-group of size 1 repeatedly).
4. One pass: right - left iterations rewire the segment in place.

Time: O(n)  |  Space: O(1)

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        start = prev.next
        then = start.next
        for _ in range(right - left):
            start.next = then.next
            then.next = prev.next
            prev.next = then
            then = start.next
        return dummy.next

Explanation:

1. Same anchor setup with dummy head and prev before the segment.
2. start stays fixed at the original left boundary; then is the node being moved.
3. Each step: Detach then, insert it right after prev, advance then.
4. Result: Nodes from left to right end up reversed while the rest of the list stays connected.

Time: O(n)  |  Space: O(1)

Problem 3: Reverse Nodes in k-Group (Leetcode:25)

Problem Statement

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

Follow-up: Can you solve the problem in O(1) extra memory space?

Code and Explanation

Approach 1 — Dummy Head + Iterative Group ReverseApproach 2 — Recursive

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next

            group_next = kth.next
            prev, curr = kth.next, group_prev.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt

            tmp = group_prev.next
            group_prev.next = kth
            group_prev = tmp

Explanation:

1. Dummy head: group_prev tracks the node before each k-group.
2. Find kth node: Advance k steps; if fewer than k nodes remain, stop.
3. Reverse group: Standard in-place reversal between group_prev.next and kth.
4. Reconnect: Link reversed segment; move group_prev to the tail of the just-reversed group (old group_prev.next).

Time: O(n)  |  Space: O(1)

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        curr = head
        count = 0
        while curr and count < k:
            curr = curr.next
            count += 1
        if count < k:
            return head

        prev, curr = None, head
        for _ in range(k):
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt

        head.next = self.reverseKGroup(curr, k)
        return prev

Explanation:

1. Count k nodes: If the remaining list is shorter than k, return as-is.
2. Reverse first k nodes iteratively within the recursive frame.
3. Recurse on remainder: Attach the result to head.next (old head becomes group tail).
4. Return prev: New head of the reversed group.

Time: O(n)  |  Space: O(n/k) recursion depth

Problem 4: Reorder List (Leetcode:143)

Problem Statement

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → ... → Ln - 1 → Ln

Reorder the list to be on the following form:

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Code and Explanation

Approach 1 — Find Middle + Reverse + MergeApproach 2 — Stack-Assisted Merge

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev

        first = head
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

Explanation:

1. Find middle: Fast/slow stops slow at the last node of the first half.
2. Split: Cut the list at slow; reverse the second half.
3. Zip merge: Alternate nodes from first and second halves.
4. In-place: No new nodes — only pointer rewiring.

Time: O(n)  |  Space: O(1)

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head:
            return
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        stack = []
        curr = slow.next
        slow.next = None
        while curr:
            stack.append(curr)
            curr = curr.next

        first = head
        while stack:
            node = stack.pop()
            tmp = first.next
            first.next = node
            node.next = tmp
            first = tmp

Explanation:

1. Same split at the middle using fast/slow.
2. Push second half onto a stack (gives reverse order).
3. Interleave: Pop from stack and splice between first-half nodes.
4. Trade-off: O(n) extra space for the stack, but easier to follow.

Time: O(n)  |  Space: O(n)

Problem 5: Rotate List (Leetcode:61)

Problem Statement

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Example 2:

Input: head = [0,1,2], k = 4
Output: [2,0,1]

Constraints:

• The number of nodes in the list is in the range [0, 500].
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

Code and Explanation

Approach 1 — Find Length + Make Circular + BreakApproach 2 — Two Pointers (k steps from tail)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        length = 1
        tail = head
        while tail.next:
            tail = tail.next
            length += 1

        k %= length
        if k == 0:
            return head

        tail.next = head
        steps = length - k
        new_tail = head
        for _ in range(steps - 1):
            new_tail = new_tail.next

        new_head = new_tail.next
        new_tail.next = None
        return new_head

Explanation:

1. Get length and tail in one walk.
2. Normalize k: k % length handles k > length.
3. Make circular: Connect tail.next to head.
4. Break at new tail: Walk length - k steps from head; the next node is the new head.

Time: O(n)  |  Space: O(1)

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head:
            return head

        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next
        k %= length
        if k == 0:
            return head

        fast = head
        for _ in range(length - k):
            fast = fast.next

        new_head = fast.next
        fast.next = None

        curr = new_head
        while curr.next:
            curr = curr.next
        curr.next = head
        return new_head

Explanation:

1. Count length and reduce k modulo length.
2. Advance fast by length - k steps — it lands on the new tail.
3. Split: fast.next is the new head; set fast.next = None.
4. Attach old head: Walk to the new tail and link back to the old head.

Time: O(n)  |  Space: O(1)

3. Dummy Node Technique

Problem 1: Remove N-th Node From End of List (Leetcode:19)

Problem Statement

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]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Code and Explanation

Approach 1 — Dummy Head + Two Pointers (Gap n)Approach 2 — Two Pass (Count Length)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

Explanation:

1. Dummy head: Handles deleting the actual head node cleanly.
2. Create gap: Advance fast n steps ahead of slow.
3. Move together: When fast reaches the last node, slow is just before the target.
4. Delete: Skip the nth-from-end node via slow.next = slow.next.next.

Time: O(n)  |  Space: O(1)

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        dummy = ListNode(0, head)
        curr = dummy
        for _ in range(length - n):
            curr = curr.next
        curr.next = curr.next.next
        return dummy.next

Explanation:

1. First pass: Count total nodes.
2. Second pass: Walk length - n steps from dummy to the predecessor.
3. Delete and return: Same skip logic; dummy head covers the head-deletion edge case.

Time: O(n)  |  Space: O(1)

Problem 2: Delete Node in a Linked List (Leetcode:237)

Problem Statement

There is a singly-linked list head and we want to delete a node node in it.

You are given the node to be deleted node. You will not be given access to the first node of head.

All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.

Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:

• The value of the given node should not exist in the linked list.
• The number of nodes in the linked list should decrease by one.
• All the values before node should be in the same order.
• All the values after node should be in the same order.

Custom testing:

• For the input, you should provide the entire linked list head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
• We will build the linked list and pass the node to your function.
• The output will be the entire list after calling your function.

Example 1:

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]
Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.

Example 2:

Input: head = [4,5,1,9], node = 1
Output: [4,5,9]
Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.

Constraints:

• The number of the nodes in the given list is in the range [2, 1000].
• -1000 <= Node.val <= 1000
• The value of each node in the list is unique.
• The node to be deleted is in the list and is not a tail node.

Code and Explanation

Approach 1 — Copy Next Node's ValueApproach 2 — Why Head Deletion Fails Here

class Solution:
    def deleteNode(self, node: ListNode) -> None:
        node.val = node.next.val
        node.next = node.next.next

Explanation:

1. No head access: We cannot reach the predecessor of node.
2. Overwrite: Copy the next node's value into node.
3. Skip next: Point node.next past the next node — effectively deleting node's original value.
4. Constraint: Only works because node is guaranteed not to be the tail.

Time: O(1)  |  Space: O(1)

# Cannot delete the head without access to head pointer.
# If head must be deleted, the caller must reassign:
# head = head.next
#
# This problem deliberately omits head to teach the
# "copy-forward" trick for interior node deletion.
class Solution:
    def deleteNode(self, node: ListNode) -> None:
        if not node.next:
            return
        node.val = node.next.val
        node.next = node.next.next

Explanation:

1. Standard deletion needs the previous node's pointer (prev.next = node.next).
2. Without head, only interior nodes can be removed via value-copying.
3. Head deletion requires the caller to update the head reference — not possible inside this API.

Time: O(1)  |  Space: O(1)

Problem 3: Remove Linked List Elements (Leetcode:203)

Problem Statement

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

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, 104].
• 1 <= Node.val <= 50
• 0 <= val <= 50

Code and Explanation

Approach 1 — Dummy HeadApproach 2 — Recursive

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next:
            if prev.next.val == val:
                prev.next = prev.next.next
            else:
                prev = prev.next
        return dummy.next

Explanation:

1. Dummy head: Handles cases where the head itself equals val.
2. Check prev.next: If it matches val, skip it without advancing prev.
3. Otherwise advance: Move prev forward only when the next node is kept.
4. Return dummy.next: The new list head after all removals.

Time: O(n)  |  Space: O(1)

class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        if not head:
            return None
        head.next = self.removeElements(head.next, val)
        return head.next if head.val == val else head

Explanation:

1. Recurse on tail: Clean the rest of the list first.
2. Filter current: If head.val == val, return head.next; otherwise keep head.
3. Builds answer from the back of the list forward.

Time: O(n)  |  Space: O(n) recursion stack

Problem 4: Odd Even Linked List (Leetcode:328)

Problem Statement

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

The first node is considered odd, and the second node is even, and so on.

Note that the relative order inside both the even and odd groups should remain as it was in the input.

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [1,3,5,2,4]

Example 2:

Input: head = [2,1,3,5,6,4,7]
Output: [2,3,6,7,1,5,4]

Constraints:

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

Code and Explanation

Approach 1 — Two Pointer ChainsApproach 2 — Collect Then Reconnect

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        odd = head
        even = even_head = head.next
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = even_head
        return head

Explanation:

1. Two chains: odd builds the odd-index chain; even builds the even-index chain.
2. Alternate links: Odd takes even.next, then even takes odd.next.
3. Append evens: Connect odd.next to even_head at the end.
4. O(1) space: Only pointer rewiring, no extra structures.

Time: O(n)  |  Space: O(1)

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        odd_nodes, even_nodes = [], []
        idx = 1
        while head:
            if idx % 2 == 1:
                odd_nodes.append(head)
            else:
                even_nodes.append(head)
            head = head.next
            idx += 1
        for i in range(len(odd_nodes) - 1):
            odd_nodes[i].next = odd_nodes[i + 1]
        for i in range(len(even_nodes) - 1):
            even_nodes[i].next = even_nodes[i + 1]
        if odd_nodes:
            odd_nodes[-1].next = even_nodes[0] if even_nodes else None
        if even_nodes:
            even_nodes[-1].next = None
        return odd_nodes[0] if odd_nodes else None

Explanation:

1. Separate by index into two node lists.
2. Rewire each chain internally, then join odd tail to even head.
3. Trade-off: Uses O(n) auxiliary arrays — violates the O(1) space constraint but illustrates the grouping logic.

Time: O(n)  |  Space: O(n)

4. Recursion on Linked List

Problem 1: Reverse Linked List (Recursive) (Leetcode:206)

Problem Statement

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

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

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

Example 3:

Input: head = []
Output: []

Constraints:

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

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Code and Explanation

Approach 1 — RecursiveApproach 2 — Iterative (for comparison)

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

Explanation:

1. Base case: Single node or empty list needs no reversal.
2. Recurse: Reverse the sublist starting at head.next; new_head is the new list head.
3. Rewire: head.next.next = head flips the link; head.next = None prevents cycles.

Time: O(n)  |  Space: O(n) call stack

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        while head:
            nxt = head.next
            head.next = prev
            prev = head
            head = nxt
        return prev

Explanation:

1. Iterative three-pointer swap — same problem, different paradigm.
2. No recursion overhead — preferred when stack depth is a concern.

Time: O(n)  |  Space: O(1)

Problem 2: Merge Two Sorted Lists (Recursive) (Leetcode:21)

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Code and Explanation

Approach 1 — RecursiveApproach 2 — Iterative with Dummy Head

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2

Explanation:

1. Base cases: If either list is empty, return the other.
2. Pick smaller head: Attach the rest of the merge to that node's next.
3. Return chosen node as the head of the merged sublist.

Time: O(n + m)  |  Space: O(n + m) recursion stack

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = curr = ListNode(0)
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        curr.next = list1 or list2
        return dummy.next

Explanation:

1. Dummy head avoids special-casing the first merged node.
2. Compare and splice the smaller node each step.
3. Attach remainder when one list is exhausted.

Time: O(n + m)  |  Space: O(1)

Problem 3: Copy List with Random Pointer (Leetcode:138)

Problem Statement

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

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

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints:

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random is null or is pointing to some node in the linked list.

Code and Explanation

Approach 1 — Hash Map (Old → New)Approach 2 — Interweave + Split (O(1) Extra Space)

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None
        old_to_new = {}
        curr = head
        while curr:
            old_to_new[curr] = Node(curr.val)
            curr = curr.next
        curr = head
        while curr:
            old_to_new[curr].next = old_to_new.get(curr.next)
            old_to_new[curr].random = old_to_new.get(curr.random)
            curr = curr.next
        return old_to_new[head]

Explanation:

1. Pass 1: Create a copy of every node; map original → copy.
2. Pass 2: Wire next and random on copies using the map.
3. No original pointers in the new list — all references go through the map.

Time: O(n)  |  Space: O(n)

class Solution:
    def copyRandomList(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return None
        curr = head
        while curr:
            copy = Node(curr.val, curr.next)
            curr.next = copy
            curr = copy.next

        curr = head
        while curr:
            if curr.random:
                curr.next.random = curr.random.next
            curr = curr.next.next

        old, new_list = head, head.next
        while old:
            copy = old.next
            old.next = copy.next
            if copy.next:
                copy.next = copy.next.next
            old = old.next
        return new_list

Explanation:

1. Interweave: Insert each copy immediately after its original (A → A' → B → B' → …).
2. Set random: copy.random = original.random.next (the paired copy).
3. Split: Restore original next links and link copies into their own list.

Time: O(n)  |  Space: O(1) excluding output list

Problem 4: Flatten a Multilevel Doubly Linked List (Leetcode:430)

Problem Statement

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 2:

Input: head = [1,2,null,3]
Output: [1,3,2]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Example 3:

Input: head = []
Output: []
Explanation: There could be empty list in the input.

Constraints:

• The number of Nodes will not exceed 1000.
• 1 <= Node.val <= 105

Code and Explanation

Approach 1 — DFS RecursionApproach 2 — Iterative DFS (Stack)

class Solution:
    def flatten(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return head

        def dfs(node: Optional[Node]) -> Optional[Node]:
            curr = node
            last = None
            while curr:
                nxt = curr.next
                if curr.child:
                    child_last = dfs(curr.child)
                    child_last.next = nxt
                    if nxt:
                        nxt.prev = child_last
                    curr.next = curr.child
                    curr.child.prev = curr
                    curr.child = None
                    last = child_last
                else:
                    last = curr
                curr = nxt
            return last

        dfs(head)
        return head

Explanation:

1. DFS on child lists: Recursively flatten each child sublist; return its tail.
2. Splice child in: Insert flattened child between curr and curr.next.
3. Fix prev pointers for doubly-linked consistency; null out child.
4. Return tail of the flattened segment for parent-level splicing.

Time: O(n)  |  Space: O(n) recursion depth

class Solution:
    def flatten(self, head: Optional[Node]) -> Optional[Node]:
        if not head:
            return head
        stack = []
        curr = head
        while curr:
            if curr.child:
                if curr.next:
                    stack.append(curr.next)
                curr.next = curr.child
                curr.child.prev = curr
                curr.child = None
            if not curr.next and stack:
                nxt = stack.pop()
                curr.next = nxt
                nxt.prev = curr
            curr = curr.next
        return head

Explanation:

1. Stack stores next pointers deferred when a child is encountered.
2. Same splice logic as recursion, but explicit stack instead of call frames.
3. When current level ends, pop and attach the saved next sublist.

Time: O(n)  |  Space: O(n) stack

Problem 5: Add Two Numbers II (Leetcode:445)

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Follow up: Could you solve it without reversing the input lists?

Code and Explanation

Approach 1 — Reverse + Add + ReverseApproach 2 — Stack (No Reverse)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(head: Optional[ListNode]) -> Optional[ListNode]:
            prev = None
            while head:
                nxt = head.next
                head.next = prev
                prev = head
                head = nxt
            return prev

        def add(a: Optional[ListNode], b: Optional[ListNode]) -> Optional[ListNode]:
            dummy = ListNode(0)
            curr = dummy
            carry = 0
            while a or b or carry:
                s = carry
                if a:
                    s += a.val
                    a = a.next
                if b:
                    s += b.val
                    b = b.next
                carry, digit = divmod(s, 10)
                curr.next = ListNode(digit)
                curr = curr.next
            return dummy.next

        return reverse(add(reverse(l1), reverse(l2)))

Explanation:

1. Reverse both lists so digits are least-significant-first.
2. Standard carry addition (same as LeetCode 2) with a dummy head.
3. Reverse result to restore most-significant-first order.

Time: O(n + m)  |  Space: O(1) excluding output

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next

        carry = 0
        head = None
        while s1 or s2 or carry:
            s = carry
            if s1:
                s += s1.pop()
            if s2:
                s += s2.pop()
            carry, digit = divmod(s, 10)
            node = ListNode(digit)
            node.next = head
            head = node
        return head

Explanation:

1. Push all digits onto two stacks (MSD at bottom).
2. Pop and add from the ends with carry — processes MSD to LSD correctly.
3. Prepend nodes to build the result list without reversing inputs.

Time: O(n + m)  |  Space: O(n + m) for stacks

5. Cycle Detection & Manipulation

Problem 1: Remove Loop in Linked List (GFG)

Problem Statement

Given the head of a singly linked list that may contain a cycle, detect the loop and remove it by setting the tail's next pointer to null. Return the head of the list after removal.

Example 1:

Input: 1 → 2 → 3 → 4 → 2 (cycle back to node 2)
Output: 1 → 2 → 3 → 4

Example 2:

Input: 1 → 2 → 3 → 4 → 5 (no cycle)
Output: 1 → 2 → 3 → 4 → 5

Constraints:

• 0 <= number of nodes <= 10^4
• The cycle, if present, has at least one node.

Code and Explanation

Approach 1 — Floyd's Cycle Detection + BreakApproach 2 — Hash Set

class Solution:
    def removeLoop(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                while fast.next != slow:
                    fast = fast.next
                fast.next = None
                break
        return head

Explanation:

1. Detect cycle with fast/slow pointers.
2. Find cycle start by resetting slow to head and moving both 1 step.
3. Find tail of cycle: Advance fast until fast.next == slow (last node in loop).
4. Break cycle: Set fast.next = None.

Time: O(n)  |  Space: O(1)

class Solution:
    def removeLoop(self, head: Optional[ListNode]) -> Optional[ListNode]:
        seen = set()
        prev = None
        curr = head
        while curr:
            if curr in seen:
                prev.next = None
                break
            seen.add(curr)
            prev = curr
            curr = curr.next
        return head

Explanation:

1. Track visited nodes in a hash set.
2. On revisit: The previous node is the tail of the cycle — set prev.next = None.
3. Simpler logic but uses O(n) extra memory.

Time: O(n)  |  Space: O(n)

Problem 2: Find Length of Loop (GFG)

Problem Statement

Given the head of a linked list that may contain a cycle, return the number of nodes in the loop. Return 0 if there is no cycle.

Example 1:

Input: 1 → 2 → 3 → 4 → 2 (cycle)
Output: 3 (nodes 2, 3, 4 form the loop)

Example 2:

Input: 1 → 2 → 3 → 4 → 5 (no cycle)
Output: 0

Constraints:

• 0 <= number of nodes <= 10^4

Code and Explanation

Approach 1 — Floyd's + Count in LoopApproach 2 — Hash Set Until Repeat

class Solution:
    def loopLength(self, head: Optional[ListNode]) -> int:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                length = 1
                curr = slow.next
                while curr != slow:
                    length += 1
                    curr = curr.next
                return length
        return 0

Explanation:

1. Detect meeting point with Floyd's algorithm.
2. Count loop nodes: Start at slow.next, count until returning to slow.
3. No meeting: Return 0.

Time: O(n)  |  Space: O(1)

class Solution:
    def loopLength(self, head: Optional[ListNode]) -> int:
        seen = {}
        length = 0
        while head:
            length += 1
            if head in seen:
                return length - seen[head]
            seen[head] = length
            head = head.next
        return 0

Explanation:

1. Store each node's position in a hash map.
2. On repeat: Loop length = current position − first-seen position.
3. End of list: No cycle → return 0.

Time: O(n)  |  Space: O(n)

Problem 3: Check if Linked List is Circular (GFG)

Problem Statement

A circular linked list is one where the last node's next points back to the head (not merely any cycle). Given head, return true if the list is circular in this strict sense, else false.

Example 1:

Input: head → 1 → 2 → 3 → head (last points to head)
Output: true

Example 2:

Input: 1 → 2 → 3 → 4 → 2 (cycle but not to head)
Output: false

Constraints:

• 0 <= number of nodes <= 10^4

Code and Explanation

Approach 1 — Walk Until head RevisitedApproach 2 — Floyd's + Verify Cycle Start Is Head

class Solution:
    def isCircular(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        curr = head.next
        while curr and curr != head:
            curr = curr.next
        return curr == head

Explanation:

1. Start from head.next (empty single-node list is not circular by this definition).
2. Walk forward until None or back to head.
3. Circular iff we return to head.

Time: O(n)  |  Space: O(1)

class Solution:
    def isCircular(self, head: Optional[ListNode]) -> bool:
        if not head:
            return False
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                slow = head
                while slow != fast:
                    slow = slow.next
                    fast = fast.next
                return slow == head
        return False

Explanation:

1. Detect any cycle with Floyd's algorithm.
2. Find cycle entrance with the standard reset trick.
3. Strict circular check: Cycle start must equal head.

Time: O(n)  |  Space: O(1)

6. Merge Techniques

Problem 1: Merge Two Sorted Lists (Leetcode:21)

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.

Code and Explanation

Approach 1 — Iterative with Dummy HeadApproach 2 — Recursive

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = curr = ListNode(0)
        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next
        curr.next = list1 or list2
        return dummy.next

Explanation:

1. Dummy head simplifies building the merged list.
2. Compare heads of both lists; splice the smaller node.
3. Attach remainder when one list is exhausted.

Time: O(n + m)  |  Space: O(1)

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val <= list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        list2.next = self.mergeTwoLists(list1, list2.next)
        return list2

Explanation:

1. Base cases handle empty lists.
2. Pick smaller head, recursively merge the rest.
3. Elegant but uses O(n + m) stack space.

Time: O(n + m)  |  Space: O(n + m)

Problem 2: Merge k Sorted Lists (Leetcode:23)

Problem Statement

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted linked list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

• k == lists.length
• 0 <= k <= 104
• 0 <= lists[i].length <= 500
• -104 <= lists[i][j] <= 104
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 104.

Code and Explanation

Approach 1 — Min-Heap (Priority Queue)Approach 2 — Divide and Conquer Merge

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = curr = ListNode(0)
        while heap:
            val, i, node = heapq.heappop(heap)
            curr.next = node
            curr = curr.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

Explanation:

1. Seed heap with the head of each non-empty list (index i breaks value ties).
2. Pop smallest, append to result, push that node's next.
3. Always pick globally smallest among k current heads.

Time: O(N log k)  |  Space: O(k) where N = total nodes

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        def merge_two(l1, l2):
            dummy = curr = ListNode(0)
            while l1 and l2:
                if l1.val <= l2.val:
                    curr.next = l1
                    l1 = l1.next
                else:
                    curr.next = l2
                    l2 = l2.next
                curr = curr.next
            curr.next = l1 or l2
            return dummy.next

        while len(lists) > 1:
            merged = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged.append(merge_two(l1, l2))
            lists = merged
        return lists[0]

Explanation:

1. Pairwise merge lists in rounds (like merge sort).
2. Halve the number of lists each round using standard two-list merge with dummy head.
3. O(1) extra space beyond recursion/iteration overhead.

Time: O(N log k)  |  Space: O(1) excluding output

Problem 3: Add Two Numbers (Leetcode:2)

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Code and Explanation

Approach 1 — Dummy Head + Single Pass CarryApproach 2 — Recursive Carry

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = curr = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            s = carry
            if l1:
                s += l1.val
                l1 = l1.next
            if l2:
                s += l2.val
                l2 = l2.next
            carry, digit = divmod(s, 10)
            curr.next = ListNode(digit)
            curr = curr.next
        return dummy.next

Explanation:

1. Digits are LSD-first — add position by position.
2. Track carry across all three conditions (l1, l2, carry).
3. Dummy head builds the result list cleanly.

Time: O(max(n, m))  |  Space: O(max(n, m)) for output

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int = 0) -> Optional[ListNode]:
        if not l1 and not l2 and not carry:
            return None
        s = carry
        if l1:
            s += l1.val
            l1 = l1.next
        if l2:
            s += l2.val
            l2 = l2.next
        carry, digit = divmod(s, 10)
        node = ListNode(digit)
        node.next = self.addTwoNumbers(l1, l2, carry)
        return node

Explanation:

1. Same digit-by-digit logic expressed recursively.
2. Base case: All inputs and carry exhausted.
3. Build list from front via return chain.

Time: O(max(n, m))  |  Space: O(max(n, m)) stack

Problem 4: Merge in Between Linked Lists (Leetcode:1669)

Problem Statement

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1's nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure indicate the result:

Build the result list and return its head.

Example 1:

Input: list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
Output: [10,1,13,1000000,1000001,1000002,5]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Example 2:

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints:

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

Code and Explanation

Approach 1 — Walk to Boundaries + SpliceApproach 2 — Dummy Head for Safety

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        prev_a = list1
        for _ in range(a - 1):
            prev_a = prev_a.next

        after_b = prev_a
        for _ in range(b - a + 2):
            after_b = after_b.next

        tail2 = list2
        while tail2.next:
            tail2 = tail2.next

        prev_a.next = list2
        tail2.next = after_b
        return list1

Explanation:

1. Find prev_a: Node at index a - 1 (just before removal start).
2. Find after_b: Node at index b + 1 (first node to keep after the gap).
3. Splice list2: Connect prev_a → list2 → … → tail2 → after_b.

Time: O(n + m)  |  Space: O(1)

class Solution:
    def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        dummy = ListNode(0, list1)
        prev = dummy
        for _ in range(a):
            prev = prev.next

        after_b = prev
        for _ in range(b - a + 2):
            after_b = after_b.next

        tail2 = list2
        while tail2.next:
            tail2 = tail2.next

        prev.next = list2
        tail2.next = after_b
        return dummy.next

Explanation:

1. Dummy head variant — walk a steps from dummy to land on the node before index a.
2. Same splice logic otherwise.
3. Useful pattern when a could be 0 in generalized variants.

Time: O(n + m)  |  Space: O(1)

Problem 5: Merge Nodes in Between Zeros (Leetcode:2181)

Problem Statement

You are given the head of a linked list, which contains a series of integers separated by 0's. The beginning and end of the linked list will have Node.val == 0.

For every two consecutive 0's, merge all the nodes lying in between them into a single node whose value is the sum of all the merged nodes. The modified list should not contain any 0's.

Return the head of the modified linked list.

Example 1:

Input: head = [0,3,1,0,4,5,2,0]
Output: [4,11]
Explanation: The above figure represents the given linked list. The modified list contains

• The sum of the nodes marked in green: 3 + 1 = 4.
• The sum of the nodes marked in red: 4 + 5 + 2 = 11.

Example 2:

Input: head = [0,1,0,3,0,2,2,0]
Output: [1,3,4]
Explanation:
The above figure represents the given linked list. The modified list contains

• The sum of the nodes marked in green: 1 = 1.
• The sum of the nodes marked in red: 3 = 3.
• The sum of the nodes marked in yellow: 2 + 2 = 4.

Constraints:

• The number of nodes in the list is in the range [3, 2 * 105].
• 0 <= Node.val <= 1000
• There are no two consecutive nodes with Node.val == 0.
• The beginning and end of the linked list have Node.val == 0.

Code and Explanation

Approach 1 — In-Place Reuse NodesApproach 2 — Dummy Head + New Nodes

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        curr = head.next
        write = head
        running_sum = 0

        while curr:
            if curr.val == 0:
                write.val = running_sum
                running_sum = 0
                write = write.next
            else:
                running_sum += curr.val
            curr = curr.next

        write.next = None
        return head

Explanation:

1. Reuse existing nodes as the output list (no new allocations).
2. Accumulate sum between zeros; on hitting 0, write sum to write node.
3. Trim tail: write.next = None removes leftover zeros.

Time: O(n)  |  Space: O(1)

class Solution:
    def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = curr = ListNode(0)
        running_sum = 0
        head = head.next

        while head:
            if head.val == 0:
                curr.next = ListNode(running_sum)
                curr = curr.next
                running_sum = 0
            else:
                running_sum += head.val
            head = head.next
        return dummy.next

Explanation:

1. Dummy head builds a fresh result list.
2. Same sum-between-zeros logic but allocates new nodes.
3. Clearer separation of input scan vs output construction.

Time: O(n)  |  Space: O(k) for k merged segments

7. Pointer Manipulation / Simulation

Problem 1: Swap Nodes in Pairs (Leetcode:24)

Problem Statement

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation:

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

Example 4:

Input: head = [1,2,3]
Output: [2,1,3]

Constraints:

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

Code and Explanation

Approach 1 — Dummy Head + Iterative SwapApproach 2 — Recursive

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        while prev.next and prev.next.next:
            first = prev.next
            second = first.next
            first.next = second.next
            second.next = first
            prev.next = second
            prev = first
        return dummy.next

Explanation:

1. Dummy head handles swapping the first pair.
2. Rewire three links: first.next = second.next, second.next = first, prev.next = second.
3. Advance prev by one (to first, the new second in the pair).

Time: O(n)  |  Space: O(1)

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        first = head
        second = head.next
        first.next = self.swapPairs(second.next)
        second.next = first
        return second

Explanation:

1. Base case: 0 or 1 nodes — nothing to swap.
2. Swap current pair, recurse on the rest.
3. Return second as the new head of this sublist.

Time: O(n)  |  Space: O(n) recursion stack

Problem 2: Swapping Nodes in a Linked List (Leetcode:1721)

Problem Statement

You are given the head of a linked list, and an integer k.

Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from the end (the list is 1-indexed).

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [1,4,3,2,5]

Example 2:

Input: head = [7,9,6,6,7,8,3,0,9,5], k = 5
Output: [7,9,6,6,8,7,3,0,9,5]

Constraints:

• The number of nodes in the list is n.
• 1 <= k <= n <= 105
• 0 <= Node.val <= 100

Code and Explanation

Approach 1 — Two Pass (Find kth from Start and End)Approach 2 — One Pass with Fast Pointer

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        length = 0
        curr = head
        while curr:
            length += 1
            curr = curr.next

        kth_start = head
        for _ in range(k - 1):
            kth_start = kth_start.next

        kth_end = head
        for _ in range(length - k):
            kth_end = kth_end.next

        kth_start.val, kth_end.val = kth_end.val, kth_start.val
        return head

Explanation:

1. Count length in one pass.
2. Walk to kth from start (k - 1 steps) and kth from end (length - k steps).
3. Swap values (problem allows value swap, not pointer swap).

Time: O(n)  |  Space: O(1)

class Solution:
    def swapNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        fast = head
        for _ in range(k):
            fast = fast.next

        kth_start = head
        kth_end = head
        while fast:
            fast = fast.next
            kth_end = kth_end.next

        kth_start.val, kth_end.val = kth_end.val, kth_start.val
        return head

Explanation:

1. Advance fast k steps ahead of head.
2. Move both together until fast reaches end — kth_end is kth from end.
3. kth_start stays at the kth from beginning; swap values.

Time: O(n)  |  Space: O(1)

Problem 3: Partition List (Leetcode:86)

Problem Statement

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example 1:

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2:

Input: head = [2,1], x = 2
Output: [1,2]

Constraints:

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

Code and Explanation

Approach 1 — Two Dummy ListsApproach 2 — In-Place Two-Pointer Rebuild

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        before_dummy = before = ListNode(0)
        after_dummy = after = ListNode(0)

        while head:
            if head.val < x:
                before.next = head
                before = before.next
            else:
                after.next = head
                after = after.next
            head = head.next

        after.next = None
        before.next = after_dummy.next
        return before_dummy.next

Explanation:

1. Two dummy heads for "less than x" and "greater/equal" partitions.
2. Append each node to the appropriate chain preserving order.
3. Concatenate: before tail links to after head; terminate after tail.

Time: O(n)  |  Space: O(1)

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less_head = less = ListNode(0)
        ge_head = ge = ListNode(0)

        curr = head
        while curr:
            if curr.val < x:
                less.next = curr
                less = less.next
            else:
                ge.next = curr
                ge = ge.next
            curr = curr.next

        ge.next = None
        less.next = ge_head.next
        return less_head.next

Explanation:

1. Identical logic to Approach 1 — dual dummy-head partitioning.
2. Key invariant: Nodes are moved, not copied; relative order preserved within each partition.
3. Must set ge.next = None to avoid cycles from the original next links.

Time: O(n)  |  Space: O(1)