LeetCode - Merge Two Sorted Lists, Swift

 

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

Merge Two Sorted Lists - LeetCode

오랜만에 리트코드

- 두개의 `정렬된` 링크드 리스트를 하나의 정렬된 리스트로 만들어 내는 것

- 기본 알고리즘은 아래와 같다.

위와 같이 두개의 링크드 리스트가 있으면 각 리스트를 노드를 가리키는 참조 인스턴스가 있다.

Left와 Right의 CurrentNode의 Val중 누가 더 작은지 대소 비교를 해서 더 작은 노드를 Head의 next Node로 전달한다.

 

지금은 Left의 CurrentNode는 1이고, Right의 CurrentNode 3이므로 또 3과 1을 대소 비교 한다.

이 작업을 다음 노드가 없을 때 까지 반복 해주면 된다. 아주 간단!

 

코드로는 아래와 같다.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func mergeTwoLists(_ list1: ListNode?, _ list2: ListNode?) -> ListNode? {
        
        var leftNode = list1
        var rightNode = list2

        var head: ListNode? = ListNode(101)
        var currentNode: ListNode? = head
        while let node = currentNode {
            if leftNode != nil, rightNode != nil {
                if leftNode!.val < rightNode!.val {
                    node.next = leftNode
                    leftNode = leftNode?.next
                } else {
                    node.next = rightNode
                    rightNode = rightNode?.next
                }
            } else {
                node.next = leftNode != nil ? leftNode : rightNode
                break
            }
            currentNode = node.next
        }
        return head?.next
    }
}