Problem statement

You are given the heads node1 and node2 of two linked lists, each sorted in non-decreasing order. Merge them into one list sorted in non-increasing order (largest value first) and return its head.

Reuse the existing nodes; either list may be empty.

Example 1

Input: node1 = [5,10,15,40], node2 = [2,3,20]
Output: [40,20,15,10,5,3,2]
Explanation: All seven values, from the largest down.

Example 2

Input: node1 = [1,1], node2 = [2,4]
Output: [4,2,1,1]
Explanation: Equal values both stay.

Example 3

Input: node1 = [], node2 = [3,8,9]
Output: [9,8,3]
Explanation: With one list empty the answer is the other list reversed.

Constraints

• 0 <= number of nodes in each list <= 10^4
• The two lists hold at least one node in total
• 0 <= Node.val <= 10^5
• Both lists are sorted in non-decreasing order

Hints for Merge Two Sorted Linked Lists in Reverse Order

1. Hint 1

   An ordinary merge produces the nodes smallest first — exactly the reverse of what is wanted.

2. Hint 2

   Instead of appending each chosen node at the tail of the result, insert it at the front.

3. Hint 3

   Repeatedly take the smaller head of the two lists, detach it, and push it onto the front of the result; when one list runs out, push the rest of the other the same way.

How to solve Merge Two Sorted Linked Lists in Reverse Order

Run the usual two-pointer merge, which visits the nodes in ascending order, but prepend each visited node to the result. Prepending reverses the order, so the result comes out descending — in one pass, without a separate reversal.

Approach

1. Set result = null.
2. While either list has nodes: pick node1's head if node2 is empty or node1.val <= node2.val, otherwise node2's head; advance that list.
3. Point the picked node at result and make it the new result.
4. Return result.

Why it works

The merge visits all nodes in non-decreasing order, and pushing each onto the front of a list stores them in the reverse of the visiting order — non-increasing.

Complexity

• Time — O(n + m)
• Space — O(1)

Pitfalls

• Save the picked node's next before relinking it, or the rest of its list is lost.
• Do not stop when one list ends: its partner's remaining nodes must still be pushed (they are the largest).

Reference solution

Python

from typing import Optional

def mergeResult(node1: Optional[ListNode], node2: Optional[ListNode]) -> Optional[ListNode]:
    result = None
    while node1 or node2:
        if node2 is None or (node1 is not None and node1.val <= node2.val):
            pick, node1 = node1, node1.next
        else:
            pick, node2 = node2, node2.next
        pick.next = result
        result = pick
    return result

Java

public static ListNode mergeResult(ListNode node1, ListNode node2) {
    ListNode result = null, pick;
    while (node1 != null || node2 != null) {
        if (node2 == null || (node1 != null && node1.val <= node2.val)) { pick = node1; node1 = node1.next; }
        else { pick = node2; node2 = node2.next; }
        pick.next = result;
        result = pick;
    }
    return result;
}

C++

ListNode* mergeResult(ListNode* node1, ListNode* node2) {
    ListNode *result = nullptr, *pick;
    while (node1 || node2) {
        if (!node2 || (node1 && node1->val <= node2->val)) { pick = node1; node1 = node1->next; }
        else { pick = node2; node2 = node2->next; }
        pick->next = result;
        result = pick;
    }
    return result;
}

JavaScript

var mergeResult = function(node1, node2) {
    var result = null, pick;
    while (node1 !== null || node2 !== null) {
        if (node2 === null || (node1 !== null && node1.val <= node2.val)) { pick = node1; node1 = node1.next; }
        else { pick = node2; node2 = node2.next; }
        pick.next = result;
        result = pick;
    }
    return result;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Rotate a Linked List Medium
• Segregate Even and Odd Nodes in a Linked List Medium
• Maximum Twin Sum of a Linked List Medium
• Delete the Middle Node of a Linked List Medium
• Swapping Nodes in a Linked List Medium
• Merge In Between Linked Lists Medium