Merge Two Sorted Lists

🎯

Merge Two Sorted Lists

easyLINKED_LISTAmazonFacebookMicrosoft

Imagine you have two sorted guest lists for a party and want to combine them into one sorted list without rearranging guests manually.

💡 This problem is about merging two sorted linked lists into one sorted linked list. Beginners often struggle because linked lists require pointer manipulation rather than simple array indexing, and understanding how to merge while preserving order is key.

📋

Problem Statement

Given two sorted singly linked lists, merge them into one sorted linked list by splicing together the nodes of the first two lists. Return the head of the merged linked list.

The number of nodes in both lists is in the range [0, 10^5].-10^5 <= Node.val <= 10^5Both lists are sorted in non-decreasing order.

💡

Example

Input"list1 = [1,2,4], list2 = [1,3,4]"

Output[1,1,2,3,4,4]

We pick nodes from both lists in sorted order: 1 from list1, then 1 from list2, then 2 from list1, then 3 from list2, then 4 from list1, then 4 from list2.

• Both lists empty → return empty list
• One list empty, other non-empty → return the non-empty list
• Lists with all elements equal → merged list contains all elements in order
• Lists with negative and positive values → merged list maintains sorted order

⚠️

Common Mistakes

Not handling empty input lists

Code crashes or returns null incorrectly

✅ Add base cases to return the other list if one is empty

Forgetting to advance pointers after attaching nodes

Infinite loop or incorrect merged list

✅ Always move the current pointer forward after attaching a node

Not using a dummy node in iterative approach

Complex code with many edge cases for head node

✅ Use a dummy node to simplify head handling

Using recursion without considering stack overflow

Stack overflow on very large lists

✅ Use iterative approach for large inputs

Swapping pointers incorrectly in in-place merge without dummy

Corrupted list or infinite loop

✅ Carefully swap pointers only after updating links

🧠

Brute Force (Recursive Merge)

💡 This approach uses recursion to merge lists by always choosing the smaller head node. It helps beginners understand the problem's recursive structure but can cause stack overflow for very long lists.

Intuition

At each step, compare the heads of both lists and pick the smaller one as the next node in the merged list, then recursively merge the rest.

Algorithm

1. If either list is empty, return the other list.
2. Compare the current nodes of both lists.
3. Recursively set the next pointer of the smaller node to the result of merging the rest.
4. Return the smaller node as the head of the merged list.

💡 The recursion naturally breaks down the problem into smaller merges, but keeping track of recursive calls can be tricky at first.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

# Driver code to test
if __name__ == '__main__':
    # Helper to create linked list from list
    def create_list(arr):
        head = ListNode(arr[0]) if arr else None
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    # Helper to print linked list
    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([1,2,4])
    l2 = create_list([1,3,4])
    merged = mergeTwoLists(l1, l2)
    print_list(merged)

Line Notes

if not l1:Base case: if first list is empty, return second list directly

if not l2:Base case: if second list is empty, return first list directly

if l1.val < l2.val:Compare current nodes to decide which node to pick next

l1.next = mergeTwoLists(l1.next, l2)Recursively merge the rest of l1 with l2 and link to current node

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode merged = sol.mergeTwoLists(l1, l2);
        printList(merged);
    }

    static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) System.out.print(",");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

if (l1 == null) return l2;Return second list if first is empty, base case

if (l2 == null) return l1;Return first list if second is empty, base case

if (l1.val < l2.val)Choose node with smaller value to continue merged list

l1.next = mergeTwoLists(l1.next, l2);Recursively merge remaining nodes and link

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

// Helper functions
ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < n; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int arr1[] = {1,2,4};
    int arr2[] = {1,3,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    Solution sol;
    ListNode* merged = sol.mergeTwoLists(l1, l2);
    printList(merged);
    return 0;
}

Line Notes

if (!l1) return l2;Base case: if first list is empty, return second

if (!l2) return l1;Base case: if second list is empty, return first

if (l1->val < l2->val)Pick smaller node to continue merged list

l1->next = mergeTwoLists(l1->next, l2);Recursively merge remaining nodes and link

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function mergeTwoLists(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

// Helper to create linked list from array
function createList(arr) {
    if (arr.length === 0) return null;
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

// Helper to print linked list
function printList(node) {
    let vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

// Test
const l1 = createList([1,2,4]);
const l2 = createList([1,3,4]);
const merged = mergeTwoLists(l1, l2);
printList(merged);

Line Notes

if (!l1) return l2;Return second list if first is empty, base case

if (!l2) return l1;Return first list if second is empty, base case

if (l1.val < l2.val)Choose smaller node to continue merged list

l1.next = mergeTwoLists(l1.next, l2);Recursively merge remaining nodes and link

⏱

Complexity

TimeO(n + m)

SpaceO(n + m) due to recursion stack

Each node is visited once, but recursion adds stack frames proportional to total nodes.

💡 For lists of length 20 and 30, expect about 50 recursive calls, which is manageable but can cause stack overflow for very large lists.

Interview Verdict: Accepted but not optimal for very large lists due to recursion depth

This approach is easy to understand and implement but can fail on very large inputs due to recursion limits.

🧠

Iterative Merge Using Dummy Head

💡 This approach uses iteration and a dummy head node to merge lists in-place without recursion, avoiding stack overflow and improving efficiency.

Intuition

Use two pointers to traverse both lists, always attaching the smaller node to the merged list, and advance pointers accordingly.

Algorithm

1. Create a dummy head node to simplify edge cases.
2. Initialize a current pointer to the dummy.
3. While both lists are non-empty, compare their heads and attach the smaller node to current.next.
4. Advance the pointer of the list from which the node was taken and move current forward.
5. After the loop, attach the remaining non-empty list to current.next.
6. Return dummy.next as the head of the merged list.

💡 Using a dummy node avoids special cases for the head, making the code cleaner and easier to follow.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode()
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next

# Driver code to test
if __name__ == '__main__':
    def create_list(arr):
        head = ListNode(arr[0]) if arr else None
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([1,2,4])
    l2 = create_list([1,3,4])
    merged = mergeTwoLists(l1, l2)
    print_list(merged)

Line Notes

dummy = ListNode()Create dummy node to simplify head handling

current = dummyInitialize current pointer to build merged list

while l1 and l2:Traverse both lists until one is exhausted

current.next = l1Attach smaller node to merged list

l1 = l1.nextAdvance pointer in list from which node was taken

current = current.nextMove current pointer forward

current.next = l1 if l1 else l2Attach remaining nodes after loop ends

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode merged = sol.mergeTwoLists(l1, l2);
        printList(merged);
    }

    static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) System.out.print(",");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

ListNode dummy = new ListNode(0);Dummy node to simplify list construction

ListNode current = dummy;Pointer to track end of merged list

while (l1 != null && l2 != null)Loop until one list is exhausted

current.next = l1;Attach smaller node to merged list

l1 = l1.next;Advance pointer in chosen list

current = current.next;Move current pointer forward

current.next = (l1 != null) ? l1 : l2;Attach remaining nodes after loop

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* current = &dummy;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                current->next = l1;
                l1 = l1->next;
            } else {
                current->next = l2;
                l2 = l2->next;
            }
            current = current->next;
        }
        current->next = l1 ? l1 : l2;
        return dummy.next;
    }
};

// Helper functions
ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < n; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int arr1[] = {1,2,4};
    int arr2[] = {1,3,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    Solution sol;
    ListNode* merged = sol.mergeTwoLists(l1, l2);
    printList(merged);
    return 0;
}

Line Notes

ListNode dummy(0);Dummy node to simplify merged list construction

ListNode* current = &dummy;Pointer to track last node in merged list

while (l1 && l2)Loop until one list is empty

current->next = l1;Attach smaller node to merged list

l1 = l1->next;Advance pointer in chosen list

current = current->next;Move current pointer forward

current->next = l1 ? l1 : l2;Attach remaining nodes after loop

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function mergeTwoLists(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;
    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }
    current.next = l1 !== null ? l1 : l2;
    return dummy.next;
}

function createList(arr) {
    if (arr.length === 0) return null;
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

function printList(node) {
    let vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

const l1 = createList([1,2,4]);
const l2 = createList([1,3,4]);
const merged = mergeTwoLists(l1, l2);
printList(merged);

Line Notes

let dummy = new ListNode(0);Dummy node to simplify head handling

let current = dummy;Pointer to build merged list

while (l1 !== null && l2 !== null)Traverse both lists until one is empty

current.next = l1;Attach smaller node to merged list

l1 = l1.next;Advance pointer in chosen list

current = current.next;Move current pointer forward

current.next = l1 !== null ? l1 : l2;Attach remaining nodes after loop

⏱

Complexity

TimeO(n + m)

SpaceO(1) additional space

Each node is visited once and linked without recursion, so constant extra space is used.

💡 For lists of length 20 and 30, this means about 50 operations and no risk of stack overflow.

Interview Verdict: Accepted and preferred approach in interviews

This iterative method is efficient, safe for large inputs, and easy to explain, making it ideal for interviews.

🧠

In-Place Merge Without Dummy Node

💡 This approach merges two lists by manipulating pointers directly without using a dummy node, saving a small amount of memory but requiring careful pointer management.

Intuition

Identify the head of the merged list by comparing first nodes, then iteratively merge by adjusting next pointers to insert nodes from the second list into the first.

Algorithm

1. If either list is empty, return the other.
2. Determine the head of the merged list by comparing first nodes.
3. Use two pointers to traverse both lists, inserting nodes from the second list into the first at correct positions.
4. Advance pointers accordingly until one list is exhausted.
5. Return the head of the merged list.

💡 This method requires careful pointer updates and is more error-prone but uses no dummy node.

</>

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val > l2.val:
        l1, l2 = l2, l1
    head = l1
    while l1 and l2:
        prev = None
        while l1 and l1.val <= l2.val:
            prev = l1
            l1 = l1.next
        prev.next = l2
        l1, l2 = l2, l1
    return head

# Driver code to test
if __name__ == '__main__':
    def create_list(arr):
        head = ListNode(arr[0]) if arr else None
        current = head
        for val in arr[1:]:
            current.next = ListNode(val)
            current = current.next
        return head

    def print_list(node):
        vals = []
        while node:
            vals.append(str(node.val))
            node = node.next
        print('[' + ','.join(vals) + ']')

    l1 = create_list([1,2,4])
    l2 = create_list([1,3,4])
    merged = mergeTwoLists(l1, l2)
    print_list(merged)

Line Notes

if not l1:Return second list if first is empty

if l1.val > l2.val:Ensure l1 starts with smaller node for easier merging

while l1 and l2:Traverse both lists until one is exhausted

while l1 and l1.val <= l2.val:Advance l1 pointer while its nodes are smaller or equal

prev.next = l2Link previous node to current l2 node to insert it

l1, l2 = l2, l1Swap pointers to continue merging

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public 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 temp = l1;
            l1 = l2;
            l2 = temp;
        }
        ListNode head = l1;
        while (l1 != null && l2 != null) {
            ListNode prev = null;
            while (l1 != null && l1.val <= l2.val) {
                prev = l1;
                l1 = l1.next;
            }
            prev.next = l2;
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        return head;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        ListNode l1 = new ListNode(1, new ListNode(2, new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3, new ListNode(4)));
        ListNode merged = sol.mergeTwoLists(l1, l2);
        printList(merged);
    }

    static void printList(ListNode node) {
        while (node != null) {
            System.out.print(node.val);
            if (node.next != null) System.out.print(",");
            node = node.next;
        }
        System.out.println();
    }
}

Line Notes

if (l1 == null) return l2;Return second list if first is empty

if (l1.val > l2.val)Swap lists to ensure l1 starts with smaller node

while (l1 != null && l2 != null)Traverse both lists until one is empty

while (l1 != null && l1.val <= l2.val)Advance l1 pointer while nodes are smaller or equal

prev.next = l2;Insert l2 node after prev

ListNode temp = l1; l1 = l2; l2 = temp;Swap pointers to continue merging

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val > l2->val) swap(l1, l2);
        ListNode* head = l1;
        while (l1 && l2) {
            ListNode* prev = nullptr;
            while (l1 && l1->val <= l2->val) {
                prev = l1;
                l1 = l1->next;
            }
            prev->next = l2;
            swap(l1, l2);
        }
        return head;
    }
};

// Helper functions
ListNode* createList(int arr[], int n) {
    if (n == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < n; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

void printList(ListNode* head) {
    while (head) {
        cout << head->val;
        if (head->next) cout << ",";
        head = head->next;
    }
    cout << endl;
}

int main() {
    int arr1[] = {1,2,4};
    int arr2[] = {1,3,4};
    ListNode* l1 = createList(arr1, 3);
    ListNode* l2 = createList(arr2, 3);
    Solution sol;
    ListNode* merged = sol.mergeTwoLists(l1, l2);
    printList(merged);
    return 0;
}

Line Notes

if (!l1) return l2;Return second list if first is empty

if (l1->val > l2->val) swap(l1, l2);Ensure l1 starts with smaller node

while (l1 && l2)Traverse both lists until one is empty

while (l1 && l1->val <= l2->val)Advance l1 pointer while nodes are smaller or equal

prev->next = l2;Insert l2 node after prev

swap(l1, l2);Swap pointers to continue merging

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function mergeTwoLists(l1, l2) {
    if (!l1) return l2;
    if (!l2) return l1;
    if (l1.val > l2.val) {
        let temp = l1;
        l1 = l2;
        l2 = temp;
    }
    let head = l1;
    while (l1 !== null && l2 !== null) {
        let prev = null;
        while (l1 !== null && l1.val <= l2.val) {
            prev = l1;
            l1 = l1.next;
        }
        prev.next = l2;
        let temp = l1;
        l1 = l2;
        l2 = temp;
    }
    return head;
}

function createList(arr) {
    if (arr.length === 0) return null;
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

function printList(node) {
    let vals = [];
    while (node) {
        vals.push(node.val);
        node = node.next;
    }
    console.log('[' + vals.join(',') + ']');
}

const l1 = createList([1,2,4]);
const l2 = createList([1,3,4]);
const merged = mergeTwoLists(l1, l2);
printList(merged);

Line Notes

if (!l1) return l2;Return second list if first is empty

if (!l2) return l1;Return first list if second is empty

if (l1.val > l2.val)Swap lists to ensure l1 starts with smaller node

while (l1 !== null && l2 !== null)Traverse both lists until one is empty

while (l1 !== null && l1.val <= l2.val)Advance l1 pointer while nodes are smaller or equal

prev.next = l2;Insert l2 node after prev

let temp = l1;Store current l1 pointer before swapping

l1 = l2;Swap l1 pointer to l2

l2 = temp;Swap l2 pointer to previous l1

⏱

Complexity

TimeO(n + m)

SpaceO(1) additional space

Each node is visited once and merged in-place without extra nodes or recursion.

💡 This approach is efficient but requires careful pointer handling to avoid bugs.

Interview Verdict: Accepted, but more complex to implement correctly

Good to mention to show pointer mastery, but iterative with dummy is safer in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the iterative approach with a dummy node is the best choice because it is efficient, safe, and easy to explain.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Recursive Merge)	O(n + m)	O(n + m) recursion stack	Yes (deep recursion)	N/A	Mention only - never code for large inputs
2. Iterative Merge Using Dummy Head	O(n + m)	O(1)	No	N/A	Code this approach in 95% of interviews
3. In-Place Merge Without Dummy Node	O(n + m)	O(1)	No	N/A	Mention to show pointer mastery, but code only if confident

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying inputs and outputs, then explain the brute force recursive approach to show understanding. Next, present the iterative dummy node approach as the optimal solution. Finally, discuss edge cases and test your code thoroughly.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force recursive approach and its limitations.Explain the iterative approach using a dummy node as the preferred solution.Write clean, well-commented code for the iterative solution.Test your code with edge cases and explain your reasoning.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation, ability to handle edge cases, and efficiency in merging sorted lists without extra space or recursion overhead.

Common Follow-ups

• How would you merge k sorted lists? → Use a min-heap or divide and conquer.
• Can you do this in-place without extra nodes? → Yes, by pointer manipulation without dummy nodes.

💡 These follow-ups test your ability to generalize the solution and optimize space usage.

🔍

Pattern Recognition

When to Use

1) You have two sorted linked lists, 2) You need to combine them into one sorted list, 3) You want to do it efficiently without extra space, 4) The problem hints at merging or two-pointer technique.

Signature Phrases

merge two sorted listscombine sorted linked listsin-place merge

NOT This Pattern When

Merging arrays or sorting arrays is different because they use indexing, not pointer manipulation.

Similar Problems

Merge k Sorted Lists - generalizes merging multiple listsSort List - uses merge sort on linked listsIntersection of Two Linked Lists - also involves pointer manipulation

Practice

1. Consider the following code snippet that removes duplicates from a sorted linked list. Given the input list: 1 -> 1 -> 2, what is the output printed by the code?

easy

A. 1 1 2

B. 1 2

C. 2

D. 1

Solution

1. Step 1: Trace initial list and first iteration

   Start with current at first node (1). current.next is also 1, so duplicate detected; remove second node by linking current.next to current.next.next (node with value 2).

2. Step 2: Continue iteration

   Now current.next is 2, which differs from current.val (1), so move current to next node (2). current.next is None, loop ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Duplicates removed, final list is 1 -> 2 [OK]

Hint: Duplicates removed by skipping next pointer [OK]

Common Mistakes:

• Forgetting to move current pointer after removal

2. You are given a singly linked list and two positions left and right. The task is to reverse the nodes of the list from position left to right in-place and return the modified list. Which approach guarantees an optimal solution with O(n) time and O(n) space complexity?

easy

A. Extract the sublist, reverse it separately, then reattach it to the original list.

B. Use dynamic programming to store reversed sublists and combine them efficiently.

C. Use a recursive approach that reverses the first n nodes and recursively adjusts the rest.

D. Apply a greedy approach that swaps node values between left and right positions.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing a sublist in-place between two given positions, which suggests a partial reversal rather than full list reversal.

2. Step 2: Identify the approach that fits the constraints

   The recursive approach reverses the first n nodes and uses recursion to handle the rest, achieving O(n) time and O(n) space due to recursion stack, which is optimal for this problem.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursive reversal matches problem constraints and complexity [OK]

Hint: Partial recursive reversal fits sublist reversal best [OK]

Common Mistakes:

• Thinking greedy swaps node values suffice
• Assuming dynamic programming applies to linked list reversal
• Believing extraction and rebuild is optimal

3. Consider the following code snippet implementing the optimal rotation of a linked list. Given the list 1 -> 2 -> 3 -> None and k = 2, what is the value of new_head.val after rotation?

easy

A. 3

B. None (empty list)

C. 1

D. 2

Solution

1. Step 1: Calculate length and adjust k

   Length is 3, k=2%3=2, so rotation needed.

2. Step 2: Move fast pointer k steps ahead

   Fast moves from 1 -> 2 -> 3.

3. Step 3: Move slow and fast until fast reaches tail

   Slow moves from 1 -> 2, fast is at tail (3).

4. Step 4: Set new_head and break the list

   New head is slow.next = 3.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   New head value is 3 [OK]

Hint: Fast pointer moves k steps ahead [OK]

Common Mistakes:

• Off-by-one error in moving fast pointer
• Not adjusting k modulo length

4. Identify the bug in the following code snippet that attempts to delete a node from a singly linked list given only access to that node.

def deleteNode(node):
    node.val = node.next.val
    # Missing update of next pointer

What is the consequence of this bug?

medium

A. The list will contain duplicate values and the node is not truly deleted.

B. The node is correctly deleted with no issues.

C. The code will raise a runtime error due to null pointer dereference.

D. The node will be set to None, breaking the list.

Solution

1. Step 1: Analyze the code's effect

   Only the node's value is overwritten with the next node's value, but the next pointer is not updated.

2. Step 2: Understand the consequence

   Since next pointer is unchanged, the next node remains in the list, causing duplicate values and no actual deletion.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Next pointer must be updated to remove next node [OK]

Hint: Must update next pointer after copying value [OK]

Common Mistakes:

• Forgetting to update next pointer after copying value
• Assuming setting node to None deletes it
• Trying to delete tail node with this method

5. The following code attempts to rotate a linked list to the right by k places. Identify the line that contains a subtle bug that can cause the list to become cyclic or truncated incorrectly.

medium

A. Line: tail.next = head # make circular

B. Line: slow.next = slow # BUG: incorrect break causing cycle

C. Line: for _ in range(k): fast = fast.next

D. Line: k = k % length

Solution

1. Step 1: Understand the purpose of breaking the list

   After rotation, the list must be broken at the new tail by setting slow.next = None.

2. Step 2: Identify the bug

   The original code sets slow.next = slow, which creates a cycle instead of breaking the list.

3. Step 3: Correct fix

   Change to slow.next = None to properly break the list.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Correct break is slow.next = None [OK]

Hint: Break list by setting slow.next = None [OK]

Common Mistakes:

• Setting slow.next to itself or wrong node causing cycles
• Not handling k modulo length correctly
• Forgetting to make list circular before rotation