Merge Two Sorted Lists

1. Problem Description

Merge two sorted linked lists into one new sorted linked list and return it. The new list is formed by splicing together all nodes from the two given lists.

2. Approach

1. Approach 1
   • Merge sort
   • Appending when one linked list is empty

3. Implementation

3.1. Merge Sort

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode{
        Val: -1,
        Next: nil,
    }
    head := dummyHead
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            head.Next = l1
            l1 = l1.Next
        }else {
            head.Next = l2
            l2 = l2.Next
        }
        head = head.Next
    }

    for l1 != nil {
        head.Next = l1
        l1 = l1.Next
        head = head.Next
    }

    for l2 != nil {
        head.Next = l2
        l2 = l2.Next
        head = head.Next
    }

    return dummyHead.Next
}

4. References

• 21. Merge Two Sorted Lists - LeetCode