https://leetcode.com/problems/merge-two-sorted-lists/

Leetcode: 21. Merge Two Sorted Lists (100%)

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil {
        return list2
    }
    if list2 == nil {
        return list1
    }
    
    // find the head
    var head *ListNode
    if list1.Val < list2.Val {
        head = list1
        list1 = list1.Next
    } else {
        head = list2
        list2 = list2.Next
    }
    
    // keep track of the start to return later
    start := head
    
    // iterate 1 head at a time, appending to head node
    for list1 != nil || list2 != nil {
        if list1 != nil {
            if list2 == nil || list1.Val < list2.Val {
                head.Next = list1
                list1 = list1.Next
            } else {
                head.Next = list2
                list2 = list2.Next
            }
        } else if list2 != nil {
            if list1 == nil || list2.Val < list1.Val {
                head.Next = list2
                list2 = list2.Next
            } else {
                head.Next = list1
                list1 = list1.Next
            }
        }
        head = head.Next
    }
    
    return start
}