Merge Sorted Linked Lists

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

```js
function mergeSortedLists(head1, head2) {
  // Fill in this method
  return head1;
}

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

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

const list2 = new Node(1);
list2.next = new Node(3);

console.log(mergeSortedLists(list1, list2));
```
```java
class Node {
  int value;
  Node next;

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

class Main {
  static Node mergeSortedLists(Node head1, Node head2) {
    // Fill in this method
    return head1;
  }

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

    Node list2 = new Node(1);
    list2.next = new Node(3);

    System.out.println(mergeSortedLists(list1, list2).value);
  }
}
```
```python
class Node:
    def __init__(self, val):
        self.value = val
        self.next = None

def mergeSortedLists(head1, head2):
    # Fill in this method
    return head1

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

list2 = Node(1)
list2.next = Node(3)

print(mergeSortedLists(list1, list2).value)
```
```cpp
#include<iostream>

struct Node{
  int value;
  Node* next;

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

Node* mergeSortedLists(Node* head1, Node* head2) {
  // Fill in this method
  return head1;
}

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

  Node* list2 = new Node(1);
  list2->next = new Node(3);

  std::cout << mergeSortedLists(list1, list2)->value;
  return 0;
}
```
```csharp
class Node {
  public int value;
  public Node next;

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

class Program {
  static Node mergeSortedLists(Node head1, Node head2) {
    // Fill in this method
    return head1;
  }

  static void Main(string[] args) {
    Node list1 = new Node(1);
    list1.next = new Node(2);

    Node list2 = new Node(1);
    list2.next = new Node(3);

    System.Console.WriteLine(mergeSortedLists(list1, list2).value);
  }
}
```
```go
package main

import "fmt"

type Node struct {
  value int
  next *Node
}

func NewNode(val int) *Node {
  return &Node{value: val, next: nil}
}

func mergeSortedLists(head1, head2 *Node) *Node {
  // Fill in this method
  return head1
}

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

  list2 := NewNode(1)
  list2.next = NewNode(3)

  fmt.Println(mergeSortedLists(list1, list2).value)
}
```