Leetcode: Merge Two Sorted Lists, 두개의 정렬된 리스트 병합

문제설명

• 두 개의 정렬된 연결 리스트를 병합하고 정렬된 리스트를 반환하라.
• 노드의 길이는 최대 0부터 50개 까지다.
• -100 <= Node.val <= 100
• l1과 l2 감소하지 않는(non-decreasing) 정렬 순서다.

문제풀이

• 반복문을 돌기전에 반환할 리스트에 더미 값을 넣자. 노드의 next값을 이어가기 위해서다. 최종 반환시 헤드를 제외하여 반환하면 된다.
• 리스트 중 하나가 nil에 도달할 때까지 리스트를 순회한다.
• 연결 리스트의 최대 길이는 50개다. 따라서, 두 리스트를 병합할 때 반복할 수 있는 최대의 수는 50*2가 된다.
• 반복문을 다 돌고나서 남아 있는 리스트를 반환하려는 병합 리스트에 그대로 이어 붙인다.

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; }
}
extension ListNode {
    func strings() -> String {
        if let nextNode = next {
            return "\(val) -> \(nextNode.strings())"
        } else {
            return "\(val)"
        }
    }
}
extension ListNode {
    static func from(arr: [Int]) -> ListNode? {
        var node = ListNode(0)
        let head = node
        for element in arr {
            let newNode = ListNode(element)
            node.next = newNode
            node = newNode
        }
        return head.next
    }
}

// Implementation
func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    let MAX_LENGTH = 50

    if l1 == nil {
        return l2
    } else if l2 == nil {
        return l1
    }

    var node1 = l1
    var node2 = l2

    // Append dummy head in the merged list
    var merged = ListNode(0)
    let head = merged

    var remainingList: ListNode?

    for _ in 0..<(MAX_LENGTH*2) { // beaware the number of iterate should be 2 * MAX_LENGTH
        guard let n1 = node1, let n2 = node2 else {
            remainingList = node1 != nil ? node1 : node2 != nil ? node2 : nil
            break
        }

        let nextNode: ListNode

        if n1.val < n2.val {
            nextNode = ListNode(n1.val)
            node1 = n1.next
        } else {
            nextNode = ListNode(n2.val)
            node2 = n2.next
        }

        merged.next = nextNode
        merged = nextNode

    }

    // exhaust remainingList
    while let node = remainingList {
        let nextNode = ListNode(node.val)
        merged.next = nextNode
        merged = nextNode
        remainingList = node.next
    }

    return head.next // except head
}

 

아래는 테스트 케이스다.
디버깅을 쉽게하기 위해 extension을 사용하여 로그와 ListNode 생성을 위한 편의 메서드를 추가하였다.

 

// TEST

var l1 = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))
var l2 = ListNode(1, ListNode(5, ListNode(6, ListNode(7))))
var merged: ListNode?
//merged = mergeTwoLists(l1, l2)
//print(merged!.strings()) // 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7

l1 = ListNode(1, ListNode(8))
l2 = ListNode(1, ListNode(5, ListNode(6, ListNode(7))))
//merged = mergeTwoLists(l1, l2)
//print(merged!.strings()) // 1 -> 5 -> 6 -> 7 -> 8

l1 = ListNode(1, ListNode(2))
l2 = ListNode(3, ListNode(5, ListNode(6, ListNode(7))))
//merged = mergeTwoLists(l1, l2)
//print(merged!.strings()) // 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8

l1 = ListNode(3, ListNode(5, ListNode(6, ListNode(7))))
l2 = ListNode(1, ListNode(2))
//merged = mergeTwoLists(l1, l2)
//print(merged!.strings()) // 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8

// case when parameters are null
//print(mergeTwoLists(nil, nil)) // nil
//print(mergeTwoLists(nil, l2)!.strings()) // 1 -> 2
//print(mergeTwoLists(l2, nil)!.strings()) // 1 -> 2


l1 = ListNode(1, ListNode(5, ListNode(6, ListNode(8))))
l2 = ListNode(2, ListNode(3, ListNode(9)))
//merged = mergeTwoLists(l1, l2)
//print(merged!.strings()) // 1 -> 2 -> 3 -> 5 -> 6 -> 8 -> 9

let list1 = [-30,-27,-27,-23,-23,-22,-21,-21,-19,-19,-16,-16,-15,-13,-9,-9,-5,-5,-3,-2,0,5,5,6,6,7,7,8,9,9,11,11,12,16,20,22,23,23,24,25,25,26]
let list2 = [-25,-25,-22,-20,-18,-17,-11,-2,-2,5,9,13,21,28,28,29]

merged = mergeTwoLists(ListNode.from(arr: list1), ListNode.from(arr: list2))
//print(merged!.strings())