🚀 Blog 3: Linked List Patterns — Expedia DSA Prep

In Expedia’s coding interviews, Linked List problems appear often because they test:

• Careful handling of null pointers
• In-place manipulation (no extra memory)
• Understanding of recursion vs iteration

We’ll cover:

1. Merge Two Sorted Lists
2. Add Two Numbers (Linked List Representation)
3. Reverse a Linked List (Iterative & Recursive)

---

🔹 Problem 1: Merge Two Sorted Lists

Pattern: Two Pointers

📌 Given two sorted linked lists, merge them into a single sorted list.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class MergeSortedLists {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

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

---

🔹 Problem 2: Add Two Numbers (Linked List Representation)

Pattern: Simulation of digit-wise addition

📌 Numbers are stored in reverse order, add them and return as linked list.

public class AddTwoNumbers {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;
            if (l1 != null) { sum += l1.val; l1 = l1.next; }
            if (l2 != null) { sum += l2.val; l2 = l2.next; }

            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }

        return dummy.next;
    }
}

✅ Example: (2 → 4 → 3) + (5 → 6 → 4) = (7 → 0 → 8)

---

🔹 Problem 3: Reverse a Linked List

Pattern: Iterative & Recursive

Iterative

public class ReverseList {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null, curr = head;

        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}

Recursive

public class ReverseListRecursive {
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

---

📊 Expedia Linked List Key Insights

• Merging & Reversing are basic building blocks.
• Digit-based addition problems are popular because they test careful pointer logic.
• Iterative vs Recursive reversal is a classic discussion point in Expedia interviews.

---

👉 In Blog 4, we’ll jump into Trees & Graphs (Vertical Traversal, Root-to-Leaf Path Sum, Number of Islands).

---