Good morning! Here's our prompt for today.

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:

1type Node struct {
2    value int
3    next *Node
4}
5
6func newNode(val int) *Node {
7    return &Node{value: val}
8}
9
10func main() {
11    list1 := newNode(1)
12    list1.next = newNode(2)
13    
14    fmt.Printf("%d -> %d", list1.value, list1.next.value)
15}

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

1// List 1: list1 := []int{1, 5, 6}
2// List 2: list2 := []int{2, 3, 4}
3
4mergedList := mergeSortedLists(list1, list2)
5// 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

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

​

package main

​

import "fmt"

​

func mergeSortedLists(l1 *Node, l2 *Node) *Node {

  // fill in this function

  return &Node{}

}

​

type Node struct {

  val  int

  next *Node

}

type LinkedList struct {

  head *Node

  tail *Node

}

​

func NewLinkedListNode(val int) Node {

  return Node{

    val:  val,

    next: nil,

  }

}

​

func (this *LinkedList) Append(newVal int) {

  newNode := NewLinkedListNode(newVal)

  if this.head == nil {

    this.head = &newNode

Tired of reading? Watch this video explanation!

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's our guided, illustrated walk-through.

How do I use this guide?