Linked List – DSA Notes

9/3/2025

Core singly/doubly list routines: reverse, middle, merge, k-groups, palindrome, cycles and more.

📌 Summary Table

Problem	Pattern	Time	Space
Reverse Linked List (Iterative)	Pointer rewiring	O(n)	O(1)
Reverse Linked List (Tail Recursion)	Tail recursion	O(n)	O(n) stack
Middle of Linked List	Tortoise–Hare	O(n)	O(1)
Remove Elements (Recursion)	Recurrence on next	O(n)	O(n) stack
Merge Two Sorted Lists (In-place)	Splice nodes	O(m+n)	O(1)
Remove N-th From End	Two pointers + dummy	O(n)	O(1)
Delete Given Node	Copy next into current	O(1)	O(1)
Odd–Even Linked List	Two lanes stitching	O(n)	O(1)
Add Two Numbers	School addition	O(max(m,n))	O(1) excl. output
Intersection of Two Lists	A+B, B+A trick	O(m+n)	O(1)
Detect Cycle (Floyd)	Slow/Fast pointers	O(n)	O(1)
Reverse Nodes in k-Group	Head-insertion k times	O(n)	O(1)
Palindrome Linked List	Reverse 2nd half	O(n)	O(1)
Detect Cycle II (Start)	Floyd + reset	O(n)	O(1)
Flatten a Linked List (bottom)	Merge vertically	O(N)	O(1)
Rotate List	Make ring, break	O(n)	O(1)
Copy List w/ Random (O(1) extra)	Interweave clones	O(n)	O(1) extra
Sort List (Merge Sort)	Split & merge	O(n log n)	O(log n) stack

Reverse Linked List (Iterative)

Problem. Reverse a singly linked list in-place.

Idea.
Walk through nodes, rewiring next to point backward with prev/cur/nxt.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head;
        while (cur != null) {
            ListNode nxt = cur.next; // store next
            cur.next = prev;         // reverse link
            prev = cur;              // advance prev
            cur = nxt;               // advance cur
        }
        return prev; // new head
    }
}

Key Takeaway. Three-pointer prev/cur/next rewiring pattern.

Reverse Linked List (Tail Recursion)

Problem. Reverse a list using recursion.

Idea. Pass prev along; recursion mimics the iterative rewiring.

Complexity. O(n) time, O(n) stack.

class Solution {
    public ListNode reverseList(ListNode head) { return rev(null, head); }

    private ListNode rev(ListNode prev, ListNode cur) {
        if (cur == null) return prev;     // base: prev is new head
        ListNode nxt = cur.next;          // store next
        cur.next = prev;                  // reverse
        return rev(cur, nxt);             // move forward
    }
}

Key Takeaway. Tail recursion = iterative logic expressed recursively.

Middle of Linked List (Tortoise–Hare)

Problem. Return middle node (if even length, return second middle).

Idea. Move slow by 1 and fast by 2.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;         // +1
            fast = fast.next.next;    // +2
        }
        return slow;
    }
}

Key Takeaway. Two-speed pointers find mid elegantly.

Remove Linked List Elements (Recursion)

Problem. Remove all nodes with value val.

Idea. Solve for head.next, then decide to keep or skip head.

Complexity. O(n) time, O(n) stack.

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if (head == null) return null;
        head.next = removeElements(head.next, val); // clean tail
        return head.val == val ? head.next : head;  // keep/skip head
    }
}

Key Takeaway. Post-order recursion on next then decide.

Merge Two Sorted Lists (In-place)

Problem. Merge two sorted lists without extra nodes.

Idea. Ensure l1.val <= l2.val, then splice runs until exhausted.

Complexity. O(m+n) time, O(1) space.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val) { ListNode t = l1; l1 = l2; l2 = t; } // l1 head is smaller
        ListNode res = l1;

        while (l1 != null && l2 != null) {
            ListNode prev = null;
            // advance l1 while it stays <= l2
            while (l1 != null && l1.val <= l2.val) { prev = l1; l1 = l1.next; }
            // splice l2 block after prev
            prev.next = l2;
            // swap roles to keep invariant
            ListNode t = l1; l1 = l2; l2 = t;
        }
        return res;
    }
}

Key Takeaway. Keep smaller list as primary and splice the other in.

Remove N-th Node From End

Problem. Remove the n-th node from the end in one pass.

Idea. Use a dummy head; advance fast n steps, then move both until fast is at tail.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head), slow = dummy, fast = dummy;
        for (int i = 0; i < n; i++) fast = fast.next;   // gap n
        while (fast.next != null) { slow = slow.next; fast = fast.next; }
        slow.next = slow.next.next; // delete target
        return dummy.next;
    }
}

Key Takeaway. Dummy node + two pointers avoids edge cases.

Delete Given Node (Only Node Ref)

Problem. Delete a node when only pointer to that node is given (non-tail).

Idea. Copy next node’s data and bypass it.

Complexity. O(1) time, O(1) space.

class Solution {
    public void deleteNode(ListNode node) {
        node.val = node.next.val;         // copy data
        node.next = node.next.next;       // skip next
    }
}

Key Takeaway. Overwrite with next; only works if node is not tail.

Odd–Even Linked List

Problem. Group odd-indexed nodes followed by even-indexed nodes (1-indexed).

Idea. Keep two chains (odd and even), then stitch.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode odd = head, even = head.next, evenHead = even;
        while (even != null && even.next != null) {
            odd.next = even.next; odd = odd.next;   // link odd chain
            even.next = odd.next; even = even.next; // link even chain
        }
        odd.next = evenHead; // stitch
        return head;
    }
}

Key Takeaway. Maintain two lanes and stitch at the end.

Add Two Numbers

Problem. Add two numbers where digits are stored in reverse order.

Idea. Walk both lists, sum digits + carry, create output nodes.

Complexity. O(max(m,n)) time, O(1) extra (excluding result list).

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry + (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0);
            carry = sum / 10;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

Key Takeaway. Digit-by-digit with carry (schoolbook addition).

Intersection of Two Linked Lists (Two Pointers)

Problem. Find the node where two singly linked lists intersect (or null).

Idea. Traverse A then B for pointer a, and B then A for pointer b. They align by length.

Complexity. O(m+n) time, O(1) space.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        ListNode a = headA, b = headB;
        while (a != b) {                 // both will traverse A+B
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }
        return a; // either intersection or null
    }
}

Key Takeaway. The A+B / B+A trick equalizes path lengths.

Detect Cycle (Floyd)

Problem. Determine if a cycle exists in a linked list.

Idea. Tortoise–Hare; if they ever meet, a cycle exists.

Complexity. O(n) time, O(1) space.

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) return true; // met inside cycle
        }
        return false;
    }
}

Key Takeaway. Floyd’s = detect cycle with two speeds.

Reverse Nodes in k-Group

Problem. Reverse nodes in groups of size k; leftover < k stays as-is.

Idea. For each block of size k, do head-insertion k-1 times.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        ListNode dummy = new ListNode(0); dummy.next = head;
        ListNode cur = dummy, nxt = dummy, pre = dummy;
        int count = 0;

        // count nodes
        while (cur.next != null) { cur = cur.next; count++; }

        // reverse each full k-block
        while (count >= k) {
            cur = pre.next;          // first node of block
            nxt = cur.next;          // node to bring to front
            for (int i = 1; i < k; i++) {
                cur.next = nxt.next; // detach nxt
                nxt.next = pre.next; // insert nxt after pre
                pre.next = nxt;      // new front becomes nxt
                nxt = cur.next;      // advance nxt
            }
            pre = cur;               // move pre to end of reversed block
            count -= k;
        }
        return dummy.next;
    }
}

Key Takeaway. Head-insertion inside each k-block.

Palindrome Linked List (Reverse Second Half)

Problem. Check if linked list is palindrome.

Idea. Find mid, reverse second half, compare halves, (optionally restore).

Complexity. O(n) time, O(1) space.

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // find middle (slow ends at first half end for even)
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

        // reverse second half starting at slow.next (for even, slow is last of first half)
        slow.next = reverse(slow.next);
        slow = slow.next; // start of reversed second half

        // compare halves
        ListNode left = head;
        while (slow != null) {
            if (left.val != slow.val) return false;
            left = left.next; slow = slow.next;
        }

        // (optional) restore: slow was reversed head; reverse again if needed
        return true;
    }

    private ListNode reverse(ListNode h) {
        ListNode prev = null, cur = h;
        while (cur != null) { ListNode nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; }
        return prev;
    }
}

Key Takeaway. Reverse 2nd half → compare → (restore optional).

Detect Cycle II (Start Node)

Problem. If a cycle exists, return the node where the cycle begins.

Idea. After meeting inside the cycle, set one pointer to head, move both 1-step; they meet at start.

Complexity. O(n) time, O(1) space.

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;
        ListNode slow = head, fast = head;

        // first meeting
        while (fast != null && fast.next != null) {
            slow = slow.next; fast = fast.next.next;
            if (slow == fast) { // cycle found
                fast = head;    // reset one pointer
                while (slow != fast) { slow = slow.next; fast = fast.next; }
                return slow;    // start of cycle
            }
        }
        return null; // no cycle
    }
}

Key Takeaway. Floyd + reset meets at cycle start.

Flatten a Linked List (Bottom Pointers)

Problem. Given a list where next links heads horizontally and each node has a sorted vertical list via bottom, flatten into one sorted bottom-linked list.

Idea. Flatten from right to left; repeatedly merge two sorted bottom-lists.

Complexity. O(N) over total nodes, O(1) extra.

class GfG {
    // merge two bottom-sorted lists
    Node merge(Node a, Node b) {
        Node dummy = new Node(0);
        Node cur = dummy;
        while (a != null && b != null) {
            if (a.data < b.data) { cur.bottom = a; a = a.bottom; }
            else { cur.bottom = b; b = b.bottom; }
            cur = cur.bottom;
        }
        cur.bottom = (a != null) ? a : b;
        return dummy.bottom;
    }

    // flatten starting from the rightmost list
    Node flatten(Node root) {
        if (root == null || root.next == null) return root;
        root.next = flatten(root.next);     // flatten rest
        root = merge(root, root.next);      // merge current with flattened rest
        return root;
    }
}

Key Takeaway. Divide-and-merge along bottom pointers.

Rotate List

Problem. Rotate list to the right by k places.

Idea. Find length, make it a ring, move len - (k % len) steps, break.

Complexity. O(n) time, O(1) space.

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;

        // compute length and get tail
        int len = 1;
        ListNode tail = head;
        while (tail.next != null) { tail = tail.next; len++; }

        // make circular
        tail.next = head;

        // find new tail: step len - (k % len) times
        k = len - (k % len);
        while (k-- > 0) tail = tail.next;

        // new head is next, break the ring
        head = tail.next;
        tail.next = null;

        return head;
    }
}

Key Takeaway. Ring trick → step → break.

Copy List with Random Pointer (O(1) extra)

Problem. Clone a list where each node has next and random pointer.

Idea.

Interleave clone nodes, 2) set random via cur.random.next, 3) split lists.

Complexity. O(n) time, O(1) extra space.

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // 1) interleave copied nodes
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }

        // 2) assign random pointers
        cur = head;
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        // 3) separate lists
        cur = head;
        Node pseudo = new Node(0), copyCur = pseudo;
        while (cur != null) {
            copyCur.next = cur.next;            // take copy
            cur.next = cur.next.next;           // restore original next
            copyCur = copyCur.next;
            cur = cur.next;
        }

        return pseudo.next;
    }
}

Key Takeaway. Interweave clones → set randoms → split.

Sort List (Merge Sort on List)

Problem. Sort a singly linked list in ascending order.

Idea. Split with slow/fast to find mid, recursively sort, then merge.

Complexity. O(n log n) time, O(log n) recursion stack.

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode mid = split(head);             // mid = start of right half
        ListNode left = sortList(head);
        ListNode right = sortList(mid);
        return merge(left, right);
    }

    // split list into [head..prev] and [slow..end]; return start of right half
    private ListNode split(ListNode head) {
        ListNode slow = head, fast = head, prev = null;
        while (fast != null && fast.next != null) {
            prev = slow; slow = slow.next; fast = fast.next.next;
        }
        prev.next = null; // cut
        return slow;      // start of right half
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode();
        ListNode t = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) { t.next = a; a = a.next; }
            else { t.next = b; b = b.next; }
            t = t.next;
        }
        t.next = (a != null) ? a : b;
        return dummy.next;
    }
}

Key Takeaway. Merge sort is natural for linked lists (no random access).