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

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

What is FAQ?

Combined Logic Steps (Both Methods Together)

⭐ Method 1: Using HashMap (Easy & Clean)
✔️ Logic Steps (with reasoning)
If head is null → return null.
Create a HashMap to map
originalNode → clonedNode.
First Pass → Create all clone nodes
Traverse the original list.
For every node, create a new node (copy).
Store:
map[orig] = copy.
Second Pass → Set next and random pointers
Traverse list again.
For each original node:
copy.next = map[original.next]
copy.random = map[original.random]
Return the cloned head
(map.get(head))

⏱️ Time Complexity: O(n)
Each node is visited twice → still O(n)
💾 Space Complexity: O(n)
Because of the HashMap storing n mappings.

⭐ Method 2: O(1) Space Optimal (Interweaving Technique)
✔️ Logic Steps (most asked in FAANG interviews)
Step 1: Insert cloned node after each original node
Original → interwoven list looks like:

A → A' → B → B' → C → C'
Do:
newNode = new Node(oldNode.val)
Insert after oldNode
Step 2: Assign random pointers for copied nodes
For each original node:
copy.random = original.random?.next
(because copied nodes are right after originals)
Step 3: Detach the two lists
Split interwoven list into:
original list
cloned list (deep copy)
Return cloned list head.

⏱️ Time Complexity: O(n)
Every node processed a constant number of times.
💾 Space Complexity: O(1)
No extra structures; only pointers used.

📌 Overall Summary (Perfect to say in Interview)
Two approaches exist:
1️⃣ HashMap Method
Create clone nodes, store in map.
Fix next & random using map.
Time: O(n)
Space: O(n) (because of map)
2️⃣ Interweaving Method (Optimal)
Insert clone nodes next to original.
Set random using original.random.next
Detach lists.
Time: O(n)
Space: O(1)

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

What is FAQ?

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

What is FAQ?

What is FAQ?

What is FAQ?

What is FAQ?

Related Posts

Leave a Comment Cancel Reply