EasyLinked list

Merge Two Sorted Lists

Q: What does the ?? operator do in the last line?

a ?? b is a when a is not null, otherwise b. After the loop at least one list is null, so list1 ?? list2 picks the one that still has nodes, or null when both are used up. It is the short form of list1 != null ? list1 : list2.

Q: Can I merge with LINQ instead?

Only by copying values out. With a helper that yields each val, Walk(list1).Concat(Walk(list2)).OrderBy(v => v) gives the merged values, and you then build new nodes. That is the collect-and-sort approach in LINQ form, O((m + n) log(m + n)), and it allocates an enumerator chain as well. LINQ has no merge operator for two sorted sequences.

Q: Why does the harness ListNode use optional constructor parameters?

public ListNode(int val = 0, ListNode next = null) lets one constructor serve as new ListNode(), new ListNode(5) and new ListNode(5, head). Optional parameters are filled in at the call site by the compiler, so there is no runtime cost compared with three overloads.

Q: How do I merge k sorted lists in C#?

Use PriorityQueue (.NET 6+): Enqueue(node, node.val) for every non-null head, then Dequeue the smallest, attach it after tail, and enqueue its next if there is one. With N nodes over k lists that is O(N log k). The queue is not stable, which does not matter here because only the values are compared.

You get list1 and list2, the first nodes of two singly linked lists. Every list node holds an integer val and a pointer next to the node after it; the last node's next is empty. Each list is sorted in ascending order, and values can repeat, inside one list and across both. Return the head of a single list that holds every value of both lists, also in ascending order. Equal values all stay: a value that appears twice in total appears twice in the result.

Either list can be empty, which means it has no nodes at all. If one list is empty, the result is the other list; if both are empty, return an empty list. You may relink the nodes you were given or build new ones; only the values in the result, from head to tail, are checked.

In the examples and test cases a list is written as an array of its values from head to tail, so [2, 5, 11] is the node 2 pointing at 5 pointing at 11.

Examples

Input

list1 = [2, 5, 11]
list2 = [3, 4, 12, 20]

Output[2, 3, 4, 5, 11, 12, 20]WhyAt each step the smaller of the two front values goes next: 2, then 3 and 4 from list2, then 5 and 11. Once list1 runs out, the rest of list2 (12, 20) follows as it is.

Input

list1 = [6, 6, 9]
list2 = [1, 6]

Output[1, 6, 6, 6, 9]WhyDuplicates are kept: 6 appears twice in list1 and once in list2, so the result holds three 6s.

Constraints

Size: 0 ≤ nodes in list1, nodes in list2 ≤ 300
Values: -10⁹ ≤ val ≤ 10⁹
Order: Both lists are sorted ascending; values can repeat.
Answer: Return the head of the merged ascending list; two empty lists merge to an empty list.
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

3 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Ignore that the inputs are sorted. Walk both lists and append every val to one Python list, call values.sort(), then build a fresh chain from the back: each new ListNode(v, head) goes in front of the one built before it, so the smallest value ends up first. Timsort spots the two ascending runs and merges them quickly, but the general bound is still O((m + n) log(m + n)) time, and the copy plus the new nodes cost O(m + n) memory.

def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    values = []
    for node in (list1, list2):
        while node:  # copy every value out of both lists
            values.append(node.val)
            node = node.next
    values.sort()
    head = None
    for v in reversed(values):  # build from the back so the smallest ends up first
        head = ListNode(v, head)
    return head

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

If one list is empty, the answer is the other one. Otherwise the smaller of the two heads is the first node of the result, and what follows it is the merge of everything else: point that node's next at the recursive call and return the node. Ties take list1 first, which is why the comparison is <=. Each call places one node, so it is O(m + n) time and O(m + n) stack frames, and Python stops at its recursion limit, 1,000 frames by default, which caps the combined length at a little under that.

def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    if list1 is None:
        return list2
    if list2 is None:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists(list1.next, list2)  # list1's head goes first
        return list1
    list2.next = merge_two_lists(list1, list2.next)
    return list2

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

Start with a throwaway dummy = ListNode() and a tail that points at it. While both lists have nodes, hang the smaller front node after tail, advance that list, and move tail on. When one list runs out, the other is already sorted, so tail.next = list1 or list2 attaches all of it in one step. The dummy means the first node needs no special case; the answer is dummy.next. Every node is relinked once and nothing new is allocated besides the dummy: O(m + n) time, O(1) extra space and no recursion limit.

def merge_two_lists(list1: ListNode | None, list2: ListNode | None) -> ListNode | None:
    dummy = ListNode()
    tail = dummy
    while list1 and list2:
        if list1.val <= list2.val:
            tail.next = list1  # take the smaller front node
            list1 = list1.next
        else:
            tail.next = list2
            list2 = list2.next
        tail = tail.next
    tail.next = list1 or list2  # one list is empty; attach the rest of the other
    return dummy.next

3 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Push every val of both lists into one array, sort it, and build a new chain from the back with new ListNode(v, head). The comparator (a, b) => a - b is not optional: without it sort() compares the numbers as strings and puts -1 before -5 and 100 before 20. O((m + n) log(m + n)) time and O(m + n) memory for the array and the new nodes; the sortedness of the inputs is not used at all.

function mergeTwoLists(list1, list2) {
  const values = [];
  for (let node = list1; node !== null; node = node.next) values.push(node.val);
  for (let node = list2; node !== null; node = node.next) values.push(node.val);
  values.sort((a, b) => a - b); // numeric order, not string order
  let head = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head); // build from the back
  return head;
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

An empty list merges to the other list. Otherwise the smaller head comes first, and its next becomes the merge of everything that remains, which is the same function on a shorter input. Ties go to list1 through the <=. One call per node gives O(m + n) time and O(m + n) stack; V8's stack is fixed, so a combined length in the high thousands ends in RangeError: Maximum call stack size exceeded, far above this problem's 600 nodes.

function mergeTwoLists(list1, list2) {
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2); // list1's head goes first
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

const dummy = new ListNode() sits in front of the result and tail walks along its end. While both lists have nodes, link the smaller front node after tail, step that list forward and move tail on. When one list runs out, the other is sorted already, so tail.next = list1 ?? list2 attaches what is left in one step. The answer is dummy.next. Each node is relinked once and only the dummy is allocated: O(m + n) time, O(1) extra space and no stack limit.

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode();
  let tail = dummy;
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1; // take the smaller front node
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 ?? list2; // one list is empty; attach the rest of the other
  return dummy.next;
}

3 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Copy every val of both lists into a number[], sort it with (a, b) => a - b (the default sort compares numbers as strings), and build a new chain from the back so the smallest value ends up first. It ignores that the inputs are sorted, so it costs O((m + n) log(m + n)) time, plus O(m + n) memory for the array and the new nodes.

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const values: number[] = [];
  for (let node = list1; node !== null; node = node.next) values.push(node.val);
  for (let node = list2; node !== null; node = node.next) values.push(node.val);
  values.sort((a, b) => a - b); // numeric order, not string order
  let head: ListNode | null = null;
  for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head); // build from the back
  return head;
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

The two null checks are the base cases, and they also narrow both parameters to ListNode for the rest of the function, so list1.val needs no !. The smaller head comes first and its next becomes the merge of what is left; ties go to list1 through the <=. One call per node: O(m + n) time and O(m + n) stack, and a combined length in the thousands ends in RangeError: Maximum call stack size exceeded.

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  if (list1 === null) return list2;
  if (list2 === null) return list1;
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2); // list1's head goes first
    return list1;
  }
  list2.next = mergeTwoLists(list1, list2.next);
  return list2;
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

const dummy = new ListNode() stands in front of the result and tail, typed ListNode, walks along its end. While both lists have nodes, link the smaller front node after tail and step that list and tail forward. When one list runs out, tail.next = list1 ?? list2 attaches the rest of the other in one step, and dummy.next is the head to return. O(m + n) time, O(1) extra space, no stack limit.

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
  const dummy = new ListNode();
  let tail: ListNode = dummy;
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      tail.next = list1; // take the smaller front node
      list1 = list1.next;
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next;
  }
  tail.next = list1 ?? list2; // one list is empty; attach the rest of the other
  return dummy.next;
}

3 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Walk both chains and add every val to an ArrayList<Integer>, which boxes each int. Collections.sort orders the boxes by value, and a loop from the last index down builds a fresh chain with new ListNode(values.get(i), head), so the smallest value ends up first. It never uses the fact that the inputs are sorted: O((m + n) log(m + n)) time and O(m + n) memory for the list and the new nodes.

import java.util.*;

public class Main {
    static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list1; node != null; node = node.next) values.add(node.val);
        for (ListNode node = list2; node != null; node = node.next) values.add(node.val);
        Collections.sort(values);
        ListNode head = null;
        for (int i = values.size() - 1; i >= 0; i--) { // build from the back so the smallest ends up first
            head = new ListNode(values.get(i), head);
        }
        return head;
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A null list merges to the other one. Otherwise the smaller head is the first node of the result, and its next is the merge of everything that remains; ties go to list1 through the <=. Each node costs one frame, so the stack grows to m + n frames. This engine starts the JVM with -Xss512k, which holds a few thousand of these small frames, comfortably more than this problem's 600 nodes, but a long enough input ends in StackOverflowError.

import java.util.*;

public class Main {
    static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2); // list1's head goes first
            return list1;
        }
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

ListNode dummy = new ListNode() sits in front of the result and tail follows its end. While both lists have nodes, link the smaller front node after tail, advance that list and move tail on. When one list is used up, the other is already in order, so a single conditional assignment attaches all of it. The head to return is dummy.next. Every node is relinked once and only the dummy is allocated: O(m + n) time, O(1) extra space, and no StackOverflowError at any length.

import java.util.*;

public class Main {
    static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1; // take the smaller front node
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = (list1 != null) ? list1 : list2; // attach the rest of the other list
        return dummy.next;
    }
}

3 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Append every Val of both lists to one []int, sort it with slices.Sort (Go 1.21+), and build a fresh chain from the back with &ListNode{Val: values[i], Next: head}, so the smallest value ends up in front. The inputs being sorted is never used: O((m + n) log(m + n)) time, and O(m + n) memory for the slice and the new nodes.

package main

import "slices"

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	var values []int
	for node := list1; node != nil; node = node.Next {
		values = append(values, node.Val)
	}
	for node := list2; node != nil; node = node.Next {
		values = append(values, node.Val)
	}
	slices.Sort(values)
	var head *ListNode
	for i := len(values) - 1; i >= 0; i-- { // build from the back so the smallest ends up first
		head = &ListNode{Val: values[i], Next: head}
	}
	return head
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A nil list merges to the other one. Otherwise the smaller head comes first and its Next becomes the merge of what is left; ties go to list1 through the <=. One call per node makes it O(m + n) time and O(m + n) stack. Goroutine stacks grow on demand, so Go reaches depths that overflow most runtimes, but the frames still cost memory.

package main

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	if list1 == nil {
		return list2
	}
	if list2 == nil {
		return list1
	}
	if list1.Val <= list2.Val {
		list1.Next = mergeTwoLists(list1.Next, list2) // list1's head goes first
		return list1
	}
	list2.Next = mergeTwoLists(list1, list2.Next)
	return list2
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

dummy := &ListNode{} is a zero-valued node that stands in front of the result, and tail follows its end. While both lists are non-nil, link the smaller front node after tail and move that list and tail forward. Go has no ternary operator, so the leftover is attached with a plain if: whichever list is still non-nil goes after tail in one step. Return dummy.Next. O(m + n) time, O(1) extra space and a constant stack.

package main

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	tail := dummy
	for list1 != nil && list2 != nil {
		if list1.Val <= list2.Val {
			tail.Next = list1 // take the smaller front node
			list1 = list1.Next
		} else {
			tail.Next = list2
			list2 = list2.Next
		}
		tail = tail.Next
	}
	if list1 != nil { // one list is empty; attach the rest of the other
		tail.Next = list1
	} else {
		tail.Next = list2
	}
	return dummy.Next
}

3 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Walk both chains and Add every val to a List<int>; it is generic over a value type, so nothing is boxed. values.Sort() orders it in place, and a loop from the last index down builds a fresh chain with new ListNode(values[i], head), so the smallest value ends up first. The sortedness of the inputs is not used: O((m + n) log(m + n)) time and O(m + n) memory for the list and the new nodes.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static ListNode MergeTwoLists(ListNode list1, ListNode list2)
    {
        var values = new List<int>();
        for (ListNode node = list1; node != null; node = node.next) values.Add(node.val);
        for (ListNode node = list2; node != null; node = node.next) values.Add(node.val);
        values.Sort();
        ListNode head = null;
        for (int i = values.Count - 1; i >= 0; i--) // build from the back so the smallest ends up first
        {
            head = new ListNode(values[i], head);
        }
        return head;
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A null list merges to the other one. Otherwise the smaller head is the first node of the result, and its next becomes the merge of what remains; ties go to list1 through the <=. One frame per node gives O(m + n) time and stack. In .NET a StackOverflowException cannot be caught: the runtime ends the process. This problem's 600 nodes are far from the 1 MB default stack, but for lists of unknown length the loop is the safe choice.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static ListNode MergeTwoLists(ListNode list1, ListNode list2)
    {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val <= list2.val)
        {
            list1.next = MergeTwoLists(list1.next, list2); // list1's head goes first
            return list1;
        }
        list2.next = MergeTwoLists(list1, list2.next);
        return list2;
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

var dummy = new ListNode() stands in front of the result (both constructor parameters are optional) and tail follows its end. While both lists have nodes, link the smaller front node after tail and advance that list and tail. When one list is used up, tail.next = list1 ?? list2 attaches the rest of the other in one step, and dummy.next is the head. O(m + n) time, O(1) extra space and no recursion.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static ListNode MergeTwoLists(ListNode list1, ListNode list2)
    {
        var dummy = new ListNode();
        ListNode tail = dummy;
        while (list1 != null && list2 != null)
        {
            if (list1.val <= list2.val)
            {
                tail.next = list1; // take the smaller front node
                list1 = list1.next;
            }
            else
            {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        tail.next = list1 ?? list2; // one list is empty; attach the rest of the other
        return dummy.next;
    }
}

3 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Push every val of both lists into a vector<int>, call sort(values.begin(), values.end()), and build a new chain from the back with new ListNode(values[i], head) so the smallest value ends up first. It does not use the order the inputs already have: O((m + n) log(m + n)) time and O(m + n) memory, and the caller now owns a second set of heap nodes besides the originals.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        vector<int> values;
        for (ListNode* node = list1; node != nullptr; node = node->next) values.push_back(node->val);
        for (ListNode* node = list2; node != nullptr; node = node->next) values.push_back(node->val);
        sort(values.begin(), values.end());
        ListNode* head = nullptr;
        for (int i = (int)values.size() - 1; i >= 0; i--) head = new ListNode(values[i], head); // build from the back
        return head;
    }
};

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A nullptr list merges to the other one. Otherwise the smaller head comes first and its next becomes the merge of what is left; ties go to list1 through the <=. One frame per node gives O(m + n) time and stack. The frames are small, so 600 nodes are nothing for a typical 8 MB thread stack, but C++ has no stack-overflow exception: a deep enough input ends in a segmentation fault.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == nullptr) return list2;
        if (list2 == nullptr) return list1;
        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2); // list1's head goes first
            return list1;
        }
        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

ListNode dummy; lives on the stack in front of the result, so there is nothing to delete, and tail starts at &dummy. While both lists have nodes, link the smaller front node after tail and advance that list and tail. When one list runs out, tail->next = list1 ? list1 : list2 attaches the rest in one step, and dummy.next is the head to return. O(m + n) time, O(1) extra space, no allocation and no recursion.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummy; // on the stack: nothing to delete
        ListNode* tail = &dummy;
        while (list1 != nullptr && list2 != nullptr) {
            if (list1->val <= list2->val) {
                tail->next = list1; // take the smaller front node
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 ? list1 : list2; // one list is empty; attach the rest of the other
        return dummy.next;
    }
};

3 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Count the nodes of both lists, malloc an int buffer of that size and copy every val into it. qsort orders the buffer; its comparator returns (x > y) - (x < y) rather than x - y, which overflows for values near ±10⁹. A loop from the last value down then mallocs one new node per value and pushes it in front of the chain, so the smallest ends up first, and the buffer is freed. The input nodes stay as they were: O((m + n) log(m + n)) time and O(m + n) memory.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

static int compareInts(const void* a, const void* b) {
    int x = *(const int*)a;
    int y = *(const int*)b;
    return (x > y) - (x < y); // x - y could overflow
}

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    int count = 0;
    for (struct ListNode* n = list1; n != NULL; n = n->next) count++;
    for (struct ListNode* n = list2; n != NULL; n = n->next) count++;
    if (count == 0) return NULL;

    int* values = malloc(count * sizeof *values);
    int i = 0;
    for (struct ListNode* n = list1; n != NULL; n = n->next) values[i++] = n->val;
    for (struct ListNode* n = list2; n != NULL; n = n->next) values[i++] = n->val;
    qsort(values, count, sizeof *values, compareInts);

    struct ListNode* head = NULL;
    for (i = count - 1; i >= 0; i--) { // build from the back so the smallest ends up first
        struct ListNode* node = malloc(sizeof *node);
        node->val = values[i];
        node->next = head;
        head = node;
    }
    free(values);
    return head;
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A NULL list merges to the other one. Otherwise the smaller head is the first node of the result, and its next becomes the merge of everything that remains; ties go to list1 through the <=. Nothing is allocated, the existing nodes are only relinked. Each node costs one stack frame, so the depth is m + n: 600 frames here is nothing, but a list of millions of nodes overflows the stack and ends the program with a segmentation fault.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) return list2;
    if (list2 == NULL) return list1;
    if (list1->val <= list2->val) {
        list1->next = mergeTwoLists(list1->next, list2); // list1's head goes first
        return list1;
    }
    list2->next = mergeTwoLists(list1, list2->next);
    return list2;
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

struct ListNode dummy is a local on the stack, so it needs no malloc and no free; tail starts at &dummy. While both lists have nodes, link the smaller front node after tail, advance that list and move tail on. When one list is used up, the other is already in order, so one assignment attaches all of it. The function returns dummy.next, a pointer into the input nodes, never the address of the local itself. O(m + n) time, O(1) extra space, no allocation and no recursion.

#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode dummy = {0, NULL}; // on the stack: only its next is used
    struct ListNode* tail = &dummy;
    while (list1 != NULL && list2 != NULL) {
        if (list1->val <= list2->val) {
            tail->next = list1; // take the smaller front node
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }
    tail->next = (list1 != NULL) ? list1 : list2; // attach the rest of the other list
    return dummy.next;
}

3 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

generateSequence(list1) { it.next } walks a chain lazily and stops at the first null; a null seed gives an empty sequence, so empty lists need no check. The two sequences are joined with +, mapped to their values, sorted and collected. foldRight then builds new nodes from the last value back to the first, so the smallest ends up at the head. It ignores that the inputs are sorted: O((m + n) log(m + n)) time and O(m + n) memory for the values and the new nodes.

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        val values = (generateSequence(list1) { it.next } + generateSequence(list2) { it.next })
            .map { it.`val` }
            .sorted()
            .toList()
        // build from the back so the smallest value ends up first
        return values.foldRight(null as ListNode?) { v, rest -> ListNode(v).also { it.next = rest } }
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A null list merges to the other one. After the two early returns both parameters are smart-cast to ListNode, since parameters are stable values. The smaller head comes first, and its next becomes the merge of what remains; the if is an expression, so each branch ends with the node it returns. Ties go to list1 through the <=. One JVM frame per node: 600 nodes is far from the limit, but very long lists throw StackOverflowError.

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        if (list1 == null) return list2
        if (list2 == null) return list1
        return if (list1.`val` <= list2.`val`) {
            list1.next = mergeTwoLists(list1.next, list2) // list1's head goes first
            list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            list2
        }
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

Parameters are read-only in Kotlin, so the loop walks two local vars, a and b. dummy sits in front of the result and tail, typed ListNode and never null, follows its end. While both lists have nodes, the smaller front node is linked after tail and becomes the new tail; assigning the smart-cast local instead of tail.next avoids a !!. Then tail.next = a ?: b attaches whatever is left. O(m + n) time, O(1) extra space and no recursion.

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var tail = dummy
        var a = list1
        var b = list2
        while (a != null && b != null) {
            if (a.`val` <= b.`val`) {
                tail.next = a // take the smaller front node
                tail = a
                a = a.next
            } else {
                tail.next = b
                tail = b
                b = b.next
            }
        }
        tail.next = a ?: b // one list is empty; attach the rest of the other
        return dummy.next
    }
}

3 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Borrow each list with as_ref() and push every val into one Vec<i32>, then sort_unstable() it; for plain integers stability does not matter and the unstable sort needs no extra buffer. into_iter().rev().fold builds the result from the largest value down, each new Box taking the chain so far as its next, so the smallest value ends up first. The input lists are dropped at the end of the call. O((m + n) log(m + n)) time and O(m + n) memory.

impl Solution {
    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut values = Vec::new();
        for list in [&list1, &list2] {
            let mut node = list.as_ref();
            while let Some(n) = node { // copy every value out
                values.push(n.val);
                node = n.next.as_ref();
            }
        }
        values.sort_unstable();
        // build from the back so the smallest value ends up first
        values.into_iter().rev().fold(None, |next, val| Some(Box::new(ListNode { val, next })))
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

match (list1, list2) takes ownership of both lists at once. The or-pattern (None, rest) | (rest, None) covers every case with an empty side and returns the other. With two nodes, the smaller head (ties go to list1) detaches its tail with take(), gets the merge of that tail and the other list as its new next, and is returned. Boxes are moved, never cloned. One frame per node: 600 is fine even in this debug build, but Rust does not guarantee tail calls, so huge lists can overflow the stack.

impl Solution {
    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match (list1, list2) {
            (None, rest) | (rest, None) => rest, // one side is empty
            (Some(mut a), Some(mut b)) => {
                if a.val <= b.val {
                    a.next = Self::merge_two_lists(a.next.take(), Some(b)); // a's head goes first
                    Some(a)
                } else {
                    b.next = Self::merge_two_lists(Some(a), b.next.take());
                    Some(b)
                }
            }
        }
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

tail is a &mut Box<ListNode> that starts at a dummy box. While both lists have a front node, pick borrows the list with the smaller front mutably; take() moves its first box out, and node.next.take() puts the rest back. tail.next.insert(node) stores the box and returns a mutable reference to it, which becomes the new tail. Finally list1.or(list2) attaches whichever list is left. O(m + n) time, O(1) extra space, every box moved once and no unsafe.

impl Solution {
    pub fn merge_two_lists(mut list1: Option<Box<ListNode>>, mut list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(0));
        let mut tail = &mut dummy;
        while let (Some(a), Some(b)) = (&list1, &list2) {
            let pick = if a.val <= b.val { &mut list1 } else { &mut list2 };
            let mut node = pick.take().unwrap(); // detach the smaller front node
            *pick = node.next.take(); // its list continues with the rest
            tail = tail.next.insert(node);
        }
        tail.next = list1.or(list2); // one list is empty; attach the other
        dummy.next
    }
}

3 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Loop over [list1, list2], an array of two optionals, and walk each one with while let current = node, appending every val to an [Int]. values.sort() sorts in place, and the rebuild walks values.reversed(), a lazy reversed view, pushing a new ListNode(value, head) in front each time so the smallest value ends up first. It ignores the input order: O((m + n) log(m + n)) time and O(m + n) memory for the array and the new nodes.

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        var values: [Int] = []
        for start in [list1, list2] {
            var node = start
            while let current = node { // copy every value out
                values.append(current.val)
                node = current.next
            }
        }
        values.sort()
        var head: ListNode? = nil
        for value in values.reversed() { // build from the back so the smallest ends up first
            head = ListNode(value, head)
        }
        return head
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

Two guard let lines unwrap the heads and return the other list when one is nil, leaving two non-optional nodes a and b. The smaller one (ties go to list1 through <=) is the first node of the result, and its next becomes the merge of what remains. ListNode is a class, so assigning a.next relinks the shared node. One stack frame per node: 600 is well within the main thread's stack, even in a debug build.

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        guard let a = list1 else { return list2 }
        guard let b = list2 else { return list1 }
        if a.val <= b.val {
            a.next = mergeTwoLists(a.next, b) // list1's head goes first
            return a
        }
        b.next = mergeTwoLists(a, b.next)
        return b
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

dummy = ListNode() sits in front of the result and tail, a non-optional ListNode, follows its end. Parameters are constants in Swift, so the loop walks two var copies. while let first = rest1, let second = rest2 runs only while both lists have a node and unwraps both; the smaller is linked after tail and becomes the new tail. Then tail.next = rest1 ?? rest2 attaches whatever is left. O(m + n) time, O(1) extra space and no force-unwraps.

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        let dummy = ListNode()
        var tail = dummy
        var rest1 = list1
        var rest2 = list2
        while let first = rest1, let second = rest2 {
            if first.val <= second.val {
                tail.next = first // take the smaller front node
                tail = first
                rest1 = first.next
            } else {
                tail.next = second
                tail = second
                rest2 = second.next
            }
        }
        tail.next = rest1 ?? rest2 // one list is empty; attach the rest of the other
        return dummy.next
    }
}

3 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

foreach ([$list1, $list2] as $node) visits both heads, and an inner for walks each chain, appending every $node->val with $values[] =. sort($values) sorts the array in place and reindexes it, and a loop from the last index down builds new nodes with new ListNode($values[$i], $head), so the smallest value ends up first. It ignores the input order: O((m + n) log(m + n)) time and O(m + n) memory.

<?php

class Solution {
    /**
     * @param ListNode|null $list1
     * @param ListNode|null $list2
     * @return ListNode|null
     */
    function mergeTwoLists(?ListNode $list1, ?ListNode $list2): ?ListNode {
        $values = [];
        foreach ([$list1, $list2] as $node) {
            for (; $node !== null; $node = $node->next) { // copy every value out
                $values[] = $node->val;
            }
        }
        sort($values);
        $head = null;
        for ($i = count($values) - 1; $i >= 0; $i--) { // build from the back so the smallest ends up first
            $head = new ListNode($values[$i], $head);
        }
        return $head;
    }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

A null list merges to the other one. Otherwise the smaller head is the first node of the result, and $this->mergeTwoLists(...) on what remains becomes its next; ties go to $list1 through <=. Objects are handles, so assigning $list1->next relinks the node in place. One call per node; PHP has no fixed recursion limit, and 600 calls are cheap.

<?php

class Solution {
    /**
     * @param ListNode|null $list1
     * @param ListNode|null $list2
     * @return ListNode|null
     */
    function mergeTwoLists(?ListNode $list1, ?ListNode $list2): ?ListNode {
        if ($list1 === null) {
            return $list2;
        }
        if ($list2 === null) {
            return $list1;
        }
        if ($list1->val <= $list2->val) {
            $list1->next = $this->mergeTwoLists($list1->next, $list2); // $list1's head goes first
            return $list1;
        }
        $list2->next = $this->mergeTwoLists($list1, $list2->next);
        return $list2;
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

$dummy = new ListNode() sits in front of the result and $tail follows its end. While both lists have nodes, the smaller front node is linked after $tail and that list moves on. When one list runs out, $list1 ?? $list2 picks the one that is not null and attaches all of it in one step; the head is $dummy->next. Every node is relinked once and only the dummy is created: O(m + n) time, O(1) extra space.

<?php

class Solution {
    /**
     * @param ListNode|null $list1
     * @param ListNode|null $list2
     * @return ListNode|null
     */
    function mergeTwoLists(?ListNode $list1, ?ListNode $list2): ?ListNode {
        $dummy = new ListNode();
        $tail = $dummy;
        while ($list1 !== null && $list2 !== null) {
            if ($list1->val <= $list2->val) {
                $tail->next = $list1; // take the smaller front node
                $list1 = $list1->next;
            } else {
                $tail->next = $list2;
                $list2 = $list2->next;
            }
            $tail = $tail->next;
        }
        $tail->next = $list1 ?? $list2; // one list is empty; attach the rest of the other
        return $dummy->next;
    }
}

3 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

[list1, list2].each walks both chains and pushes every val onto an Array with <<; while node stops at nil, so an empty list adds nothing. sort! sorts in place, and reverse_each.reduce(nil) builds new nodes from the largest value down, each ListNode.new(value, head) taking the chain so far as its next, so the smallest ends up first. O((m + n) log(m + n)) time and O(m + n) memory.

# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
  values = []
  [list1, list2].each do |node|
    while node # copy every value out
      values << node.val
      node = node.next
    end
  end
  values.sort!
  # build from the back so the smallest value ends up first
  values.reverse_each.reduce(nil) { |head, value| ListNode.new(value, head) }
end

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

Two guard clauses return the other list when one is nil. Otherwise the smaller head (ties go to list1 through <=) is the first node of the result, and its next becomes the merge of what remains. The if is an expression, so each branch ends with the node it returns. One VM frame per node: 600 is far below the depth where CRuby raises SystemStackError.

# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
  return list2 if list1.nil?
  return list1 if list2.nil?

  if list1.val <= list2.val
    list1.next = merge_two_lists(list1.next, list2) # list1's head goes first
    list1
  else
    list2.next = merge_two_lists(list1, list2.next)
    list2
  end
end

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

dummy = ListNode.new sits in front of the result and tail follows its end. while list1 && list2 runs as long as both lists have nodes; the smaller front node is linked after tail and that list moves on. When one runs out, list1 || list2 returns the one that is not nil, and it is attached in one step. The answer is dummy.next: O(m + n) time, O(1) extra space and no recursion.

# @param {ListNode} list1
# @param {ListNode} list2
# @return {ListNode}
def merge_two_lists(list1, list2)
  dummy = ListNode.new
  tail = dummy
  while list1 && list2
    if list1.val <= list2.val
      tail.next = list1 # take the smaller front node
      list1 = list1.next
    else
      tail.next = list2
      list2 = list2.next
    end
    tail = tail.next
  end
  tail.next = list1 || list2 # one list is empty; attach the rest of the other
  dummy.next
end

3 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Loop over [list1, list2] and walk each chain with a for whose node != null condition promotes the local to ListNode, adding every val to a List<int>. values.sort() sorts in place with the natural order of int, and a loop over values.reversed pushes a new ListNode(value, head) in front each time, so the smallest value ends up first. O((m + n) log(m + n)) time and O(m + n) memory.

class Solution {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    final values = <int>[];
    for (final start in [list1, list2]) {
      for (var node = start; node != null; node = node.next) {
        values.add(node.val); // copy every value out
      }
    }
    values.sort();
    ListNode? head;
    for (final value in values.reversed) {
      head = ListNode(value, head); // build from the back so the smallest ends up first
    }
    return head;
  }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

Parameters are local variables in Dart, so after if (list1 == null) return list2; and the matching check for list2, both are promoted to non-null ListNode for the rest of the method. The smaller head (ties go to list1 through <=) is the first node of the result, and its next becomes the merge of what remains. One frame per node: 600 is well within the Dart VM's stack.

class Solution {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if (list1.val <= list2.val) {
      list1.next = mergeTwoLists(list1.next, list2); // list1's head goes first
      return list1;
    }
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

final dummy = ListNode() sits in front of the result and tail, inferred as a non-null ListNode, follows its end. Dart parameters can be reassigned, so the loop walks list1 and list2 themselves; the while condition promotes both inside the body. The smaller front node is linked after tail, becomes the new tail, and its list moves on. Then tail.next = list1 ?? list2 attaches the rest. O(m + n) time, O(1) extra space and no !.

class Solution {
  ListNode? mergeTwoLists(ListNode? list1, ListNode? list2) {
    final dummy = ListNode();
    var tail = dummy;
    while (list1 != null && list2 != null) {
      if (list1.val <= list2.val) {
        tail.next = list1; // take the smaller front node
        tail = list1;
        list1 = list1.next;
      } else {
        tail.next = list2;
        tail = list2;
        list2 = list2.next;
      }
    }
    tail.next = list1 ?? list2; // one list is empty; attach the rest of the other
    return dummy.next;
  }
}

3 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · Collect every value, sort, rebuild a list

O((m + n) log(m + n)) time · O(m + n) space

Iterator.iterate(list)(_.next).takeWhile(_ != null) walks a chain lazily and stops at the first null; an empty list yields nothing. The local values helper maps each node to its x, the two iterators are joined with ++, and toArray.sorted orders the result. foldRight then builds new nodes from the last value back, each new ListNode(v, rest) taking the chain so far, so the smallest ends up first. O((m + n) log(m + n)) time and O(m + n) memory.

object Solution {
  def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode = {
    def values(list: ListNode): Iterator[Int] =
      Iterator.iterate(list)(_.next).takeWhile(_ != null).map(_.x) // every value, head to tail
    val sorted = (values(list1) ++ values(list2)).toArray.sorted
    // build from the back so the smallest value ends up first
    sorted.foldRight(null: ListNode)((v, rest) => new ListNode(v, rest))
  }
}

2 · Recursive: the smaller head, then merge the rest

O(m + n) time · O(m + n) space

The whole method is one if / else if expression. A null list merges to the other one; otherwise the smaller head (ties go to list1 through <=) is the first node of the result, and its next becomes the merge of what remains. The node's value field is x here. The call is not in tail position, since its result is assigned before the node is returned, so it uses one JVM frame per node: fine for 600 nodes.

object Solution {
  def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode =
    if (list1 == null) list2
    else if (list2 == null) list1
    else if (list1.x <= list2.x) {
      list1.next = mergeTwoLists(list1.next, list2) // list1's head goes first
      list1
    } else {
      list2.next = mergeTwoLists(list1, list2.next)
      list2
    }
}

3 · Iterative: splice behind a dummy head

O(m + n) time · O(1) space

recommended

Parameters are vals in Scala, so the loop walks two var copies, a and b. dummy = new ListNode() uses the default arguments and sits in front of the result; tail follows its end. While both lists have nodes, the smaller front node is linked after tail and that list moves on. When one is used up, an if expression attaches the other in one step, and the head is dummy.next. O(m + n) time, O(1) extra space and no recursion.

object Solution {
  def mergeTwoLists(list1: ListNode, list2: ListNode): ListNode = {
    val dummy = new ListNode()
    var tail = dummy
    var a = list1
    var b = list2
    while (a != null && b != null) {
      if (a.x <= b.x) {
        tail.next = a // take the smaller front node
        a = a.next
      } else {
        tail.next = b
        b = b.next
      }
      tail = tail.next
    }
    tail.next = if (a != null) a else b // one list is empty; attach the rest of the other
    dummy.next
  }
}

FAQ for C#

What does the ?? operator do in the last line?

a ?? b is a when a is not null, otherwise b. After the loop at least one list is null, so list1 ?? list2 picks the one that still has nodes, or null when both are used up. It is the short form of list1 != null ? list1 : list2.

Can I merge with LINQ instead?

Only by copying values out. With a helper that yields each val, Walk(list1).Concat(Walk(list2)).OrderBy(v => v) gives the merged values, and you then build new nodes. That is the collect-and-sort approach in LINQ form, O((m + n) log(m + n)), and it allocates an enumerator chain as well. LINQ has no merge operator for two sorted sequences.

Does merging change the lists that were passed in?

The recursive and dummy-head versions reuse the input nodes and rewrite their next fields, so the caller's list1 and list2 become parts of the merged chain. ListNode is a class, so the method receives references to the same objects, not copies. If you need the originals intact, use the collect-and-sort version, which builds new nodes.

Why does the harness ListNode use optional constructor parameters?

public ListNode(int val = 0, ListNode next = null) lets one constructor serve as new ListNode(), new ListNode(5) and new ListNode(5, head). Optional parameters are filled in at the call site by the compiler, so there is no runtime cost compared with three overloads.

How do I merge k sorted lists in C#?

Use PriorityQueue<ListNode, int> (.NET 6+): Enqueue(node, node.val) for every non-null head, then Dequeue the smallest, attach it after tail, and enqueue its next if there is one. With N nodes over k lists that is O(N log k). The queue is not stable, which does not matter here because only the values are compared.

Keep going

Longest Substring Without Repeating Characters18 / 40 · Sliding window · Medium

merge_two_lists.cs

C# 10.0

Not run yet

+ 8 hidden

Input

list1 = [2, 5, 11]
list2 = [3, 4, 12, 20]

Expected

[2, 3, 4, 5, 11, 12, 20]

At each step the smaller of the two front values goes next: 2, then 3 and 4 from list2, then 5 and 11. Once list1 runs out, the rest of list2 (12, 20) follows as it is.