Problem

• https://leetcode.com/problems/merge-two-sorted-lists
• https://leetcode.cn/problems/merge-two-sorted-lists (中文)

Data Structure

• Linked List

Intuition

Create a dummy node to hold the result linked list, then compare the values of the two linked lists' heads, put the smaller one to the tail of the result linked list. Then move the head of the linked list to the next node.

Code

class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {

        var list1 = list1
        var list2 = list2

        // 1. Prepare the nodes for as the result linked list
        var result: ListNode? = ListNode()
        var tail: ListNode? = result

        // 2. Routine
        while let one = list1?.val,
              let two = list2?.val {
            if one < two {
                tail?.next = list1
                list1 = list1?.next
            } else {
                tail?.next = list2
                list2 = list2?.next
            }
            tail = tail?.next
        }

        // 3. Process the remaining
        tail?.next = list1 ?? list2

        return result?.next
    }
}

Routine

Time to stop

When any of list1 or list2 is already nil, means only both are not nil then started the routine.

while let one = list1?.val, let two = list2?.val

Process

Set the smaller node to the tail

Process the remaining

When exist the while loop, there will be two cases

1. list1 or list2 is nil
2. list1 and list2 are nil

So that here we can utilize optional chain to let Swift to do the job.

tail?.next = list1 ?? list2

Returns

return result?.next

Complexity

• Time Complexity - O(m + n)
  • m is length of list1, n is length of list2
• Space Complexity - O(1)

End of post

That's it!

Please leave comment if you have any comments, thanks for your reading!