Merge Two Sorted Lists

LeetCode 21 · View on LeetCode

Use a dummy head node to avoid special-casing the first element. Compare nodes from both lists, appending the smaller one. Attach whatever remains at the end.

package main

import "fmt"

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	curr := dummy
	for l1 != nil && l2 != nil {
		if l1.Val <= l2.Val {
			curr.Next = l1
			l1 = l1.Next
		} else {
			curr.Next = l2
			l2 = l2.Next
		}
		curr = curr.Next
	}
	if l1 != nil {
		curr.Next = l1
	} else {
		curr.Next = l2
	}
	return dummy.Next
}

func printList(head *ListNode) {
	for curr := head; curr != nil; curr = curr.Next {
		fmt.Print(curr.Val, " -> ")
	}
	fmt.Println("nil")
}

func main() {
	l1 := &ListNode{1, &ListNode{3, &ListNode{5, nil}}}
	l2 := &ListNode{2, &ListNode{4, &ListNode{6, nil}}}
	merged := mergeTwoLists(l1, l2)
	printList(merged) // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nil
}