DSA – Linked List Quick Recap

Q: Linked List Cycle

🔹 Logic Initialize two pointers: slow → moves one step at a time. fast → moves two steps at a time. Traverse the linked list: Move slow by one node. Move fast by two nodes. If at any point slow === fast , a cycle exists → return true . If fast reaches null or fast.next is null , → the list has no cycle → return false . ⏱️ Time Complexity O(n) — each node is visited at most once by the pointers. 💾 Space Complexity O(1) — only constant extra space used for the two pointers.

Q: Add Two Numbers

🔹 Logic Maintain a carry/reminder (initially 0). Create a dummy head node and a pointer current . Loop while either list ( l1 or l2 ) still has nodes: - Compute: sum = l1.val + l2.val + carry - Extract digit: value = sum % 10 - Update carry: carry = Math.floor(sum / 10) - Create a new node with value and attach to result list. - Move pointers l1 , l2 , and current forward. After loop, if carry remains, add one more node. Return dummy.next as the final linked list. ⏱️ Time Complexity O(max(m, n)) You traverse both lists once, where m and n are lengths of l1 and l2 . 💾 Space Complexity O(max(m, n)) A new linked list of size equal to the sum length is created.

Q: Merge Two Sorted Lists

Logic (for understanding) Create a dummy node → helps return the final list easily. Compare values of list1 and list2 . Whichever is smaller → attach to current.next . Move forward in that list. Move current forward. After loop ends, one list may still have nodes → attach it directly. Return dummy.next . Time: O(n + m) Space: O(1) 21. Merge Two Sorted Lists

Q: Reverse Linked List II

Step 1: Create a dummy node Add a temporary dummy node before the original head. This helps handle edge cases (like reversing from position 1). Step 2: Move to the node just before left Start from the dummy node. Move forward (left − 1) times . Now you are standing at the node right before the part to reverse → call it prev . Step 3: Mark the start of the reversal Let curr point to the node at position left . This node will slowly move toward the end of the reversed section. Step 4: Reverse the sublist in-place Repeat this process (right − left) times : Pick the node right after curr → call it next . Detach next from its current position. Insert next immediately after prev . This shifts next to the front of the reversing section. This gradually reverses the nodes between left and right . Step 5: Return the new head The dummy node’s next now points to the updated head. Return it. ✅ Why This Works Instead of traditional full reversal, this method: Keeps prefix and suffix intact Only reorders the middle part using pointer shifting Complexity Time Complexity : O(n) Space Complexity : O(1) Leet Code : 92. Reverse Linked List II

Linked List Cycle

🔹 Logic
Initialize two pointers:
slow → moves one step at a time.
fast → moves two steps at a time.
Traverse the linked list:
Move slow by one node.
Move fast by two nodes.
If at any point slow === fast, a cycle exists → return true.
If fast reaches null or fast.next is null,
→ the list has no cycle → return false.

⏱️ Time Complexity
O(n) — each node is visited at most once by the pointers.
💾 Space Complexity
O(1) — only constant extra space used for the two pointers.

Add Two Numbers

🔹 Logic

Maintain a carry/reminder (initially 0).
Create a dummy head node and a pointer current.
Loop while either list (l1 or l2) still has nodes:
- Compute:
sum = l1.val + l2.val + carry
- Extract digit:
value = sum % 10
- Update carry:
carry = Math.floor(sum / 10)
- Create a new node with value and attach to result list.
- Move pointers l1, l2, and current forward.
After loop, if carry remains, add one more node.
Return dummy.next as the final linked list.

⏱️ Time Complexity
O(max(m, n))
You traverse both lists once, where m and n are lengths of l1 and l2.

💾 Space Complexity
O(max(m, n))
A new linked list of size equal to the sum length is created.

Merge Two Sorted Lists

Logic (for understanding)
Create a dummy node → helps return the final list easily.
Compare values of list1 and list2.
Whichever is smaller → attach to current.next.
Move forward in that list.
Move current forward.
After loop ends, one list may still have nodes → attach it directly.
Return dummy.next.

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

21. Merge Two Sorted Lists

Reverse Linked List II

Step 1: Create a dummy node
Add a temporary dummy node before the original head.
This helps handle edge cases (like reversing from position 1).

Step 2: Move to the node just before left
Start from the dummy node.
Move forward (left − 1) times.
Now you are standing at the node right before the part to reverse → call it prev.

Step 3: Mark the start of the reversal
Let curr point to the node at position left.
This node will slowly move toward the end of the reversed section.

Step 4: Reverse the sublist in-place
Repeat this process (right − left) times:
Pick the node right after curr → call it next.
Detach next from its current position.
Insert next immediately after prev.
This shifts next to the front of the reversing section.
This gradually reverses the nodes between left and right.

Step 5: Return the new head
The dummy node’s next now points to the updated head.
Return it.

✅ Why This Works
Instead of traditional full reversal, this method:
Keeps prefix and suffix intact
Only reorders the middle part using pointer shifting

Complexity
Time Complexity : O(n)
Space Complexity : O(1)
Leet Code : 92. Reverse Linked List II

What is FAQ?

Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat.

What is FAQ?

138. Copy List with Random Pointer 

//⭐ Version 1 — HashMap Method (Simple & Clear)
//⏱ Time: O(n)
// 💾 Space: O(n)

function copyRandomList_O1(head: Node | null): Node | null {
    if (head === null) return null;
    let curr: Node | null = head;

    // 1️⃣ Clone nodes and insert them between original nodes
    while (curr) {
        const copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }

    // 2️⃣ Assign random pointers for the copies
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next!.random = curr.random.next;
        }
        curr = curr.next!.next;
    }

    // 3️⃣ Separate the original list and the copied list
    curr = head;
    const newHead = head.next;
    while (curr) {
        const copy = curr.next!;
        curr.next = copy.next;
        copy.next = copy.next ? copy.next.next : null;
        curr = curr.next;
    }
    return newHead;
}

// ⭐ Version 2 — Interweaving Method (Optimal O(1) space)
// ⏱ Time: O(n)
// 💾 Space: O(1)

function copyRandomList_O1(head: Node | null): Node | null {
    if (head === null) return null;
    let curr: Node | null = head;

    // 1️⃣ Clone nodes and insert them between original nodes
    while (curr) {
        const copy = new Node(curr.val);
        copy.next = curr.next;
        curr.next = copy;
        curr = copy.next;
    }

    // 2️⃣ Assign random pointers for the copies
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next!.random = curr.random.next;
        }
        curr = curr.next!.next;
    }

    // 3️⃣ Separate the original list and the copied list
    curr = head;
    const newHead = head.next;
    while (curr) {
        const copy = curr.next!;
        curr.next = copy.next;
        copy.next = copy.next ? copy.next.next : null;
        curr = curr.next;
    }
    return newHead;
}

DSA – Linked List Quick Recap

Linked List Cycle

Add Two Numbers

Merge Two Sorted Lists

Reverse Linked List II

What is FAQ?

What is FAQ?

What is FAQ?

Leave a Comment Cancel Reply

Subscribe

Linked List Cycle

Add Two Numbers

Merge Two Sorted Lists

Reverse Linked List II

What is FAQ?

What is FAQ?

What is FAQ?

Related Posts

Leave a Comment Cancel Reply