Tom on the Internet
← Back

Merge Two Sorted Linked Lists

easy
Linked List

Challenge

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted linked list and return the head of the new sorted linked list.

<Code /> 

mergeTwoLists(list1, list2) {
    let dummy = { next: null }
    let cur = dummy

    while (list1 && list2) {
        if (list1.val < list2.val) {
            cur.next = list1
            list1 = list1.next
        } else {
            cur.next = list2
            list2 = list2.next
        }
        cur = cur.next
    }

    cur.next = list1 || list2
    return dummy.next
}

Thoughts

My initial attempt at this was pretty sloppy. I had quite a few conditionals just to determine which node would be the head of my new list. When I learned the dummy node solution, it made things way cleaner. Use a dummy node, add to it, and return the dummy's next at the end.