Here is the interview question prompt, presented for reference.

Write an algorithm to merge two sorted linked lists and return it as a new sorted list. The new list should be constructed by joining the nodes of the input lists.

You may assume the following node definition:

function Node(val) {
  this.value = val;
  this.next = null;
}

const list1 = new Node(1);
list1.next = new Node(2);

console.log(list1);

public class Node {
    int value;
    Node next;

    Node(int value) {
        this.value = value;
        this.next = null;
    }

    public static void main(String[] args) {
        Node list1 = new Node(1);
        list1.next = new Node(2);

        System.out.println(list1.value + " -> " + list1.next.value);
    }
}

class Node:
    def __init__(self, val):
        self.value = val
        self.next = None

list1 = Node(1)
list1.next = Node(2)

print(list1.value, '->', list1.next.value)

#include<iostream>

struct Node {
    int value;
    Node* next;

    Node(int val) : value(val), next(nullptr) {}
};

int main() {
    Node* list1 = new Node(1);
    list1->next = new Node(2);

    std::cout << list1->value << " -> " << list1->next->value << std::endl;
}

public class Node {
    public int value;
    public Node next;

    public Node(int val) {
        this.value = val;
        this.next = null;
    }
}

class Program {
    static void Main() {
        Node list1 = new Node(1);
        list1.next = new Node(2);

        Console.WriteLine("{0} -> {1}", list1.value, list1.next.value);
    }
}

type Node struct {
    value int
    next *Node
}

func newNode(val int) *Node {
    return &Node{value: val}
}

func main() {
    list1 := newNode(1)
    list1.next = newNode(2)

    fmt.Printf("%d -> %d", list1.value, list1.next.value)
}

Write a method called mergeSortedLists that would be invoked as such in the following example:

// List 1: 1 -> 5 -> 6
// List 2: 2 -> 3 -> 4

mergeSortedLists(list1, list2);
// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

// List 1: LinkedList<Integer> list1 = new LinkedList<>(Arrays.asList(1,5,6));
// List 2: LinkedList<Integer> list2 = new LinkedList<>(Arrays.asList(2,3,4));

LinkedList<Integer> mergedList = mergeSortedLists(list1, list2);
// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

// List 1: std::list<int> list1 = {1, 5, 6};
// List 2: std::list<int> list2 = {2, 3, 4};

std::list<int> mergedList = mergeSortedLists(list1, list2);
// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

# List 1: list1 = [1, 5, 6]
# List 2: list2 = [2, 3, 4]

merged_list = merge_sorted_lists(list1, list2)
# Output: [1, 2, 3, 4, 5, 6]

// List 1: List<int> list1 = new List<int> { 1, 5, 6 };
// List 2: List<int> list2 = new List<int> { 2, 3, 4 };

List<int> mergedList = MergeSortedLists(list1, list2);
// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

// List 1: list1 := []int{1, 5, 6}
// List 2: list2 := []int{2, 3, 4}

mergedList := mergeSortedLists(list1, list2)
// Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6

As you can see, the linked lists are merged in an ascending sorted order.

Constraints

• Length of the linked lists <= 100000
• The values in the nodes will be in the range -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(n) considering the call stack in recursion

You can see the full challenge with visuals at this link.