Swift) LeetCode(Easy) - Merge Two Sorted Lists(Linked List)

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

Merge Two Sorted Lists - LeetCode

안녕하세요 후르륵짭잡 입니다

이번에는 한번도 해보지 못 했던 swift로 연결리스트 구현 입니다

swift로 연결 리스트 구현은 처음이라 많이 애먹었는데요,,,,

그럼 알아 가보도록 하겠습니다.

 

** 문제 **

문제는 정렬된 두개의 연결 리스트를 주고 그 두개의 연결리스트를 묶어서 다시 정렬하는 거 입니다.

문제는 간단합니다

 

** 전체 코드 **

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 returnList(_ list : ListNode?) -> [Int]{
        
        var arrayList : [Int] = []
        
        guard var list = list else {
            return []
        }
        
        while true {
            
            arrayList.append(list.val)
            
            if let next = list.next {
                list = next
            }
            else{
                break
            }
    
        }
        
        return arrayList
    }
    
 
    
    func makeList(_ arrayList : [Int]) -> ListNode? {
        
        var returnListNode : ListNode? = nil
        var next : ListNode? = nil
        
        for item in arrayList{
            
            if returnListNode == nil {
                returnListNode = ListNode(item)
                next = returnListNode!
            }
            else{
                next!.next = ListNode(item)
                next = next!.next
            }
            
        }
        
        return returnListNode ?? nil
        
    }
    
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
     
        if l1 == nil {
            return l2
        }
        else if l2 == nil {
            return l1
        }
        else if l1 == nil && l2 == nil{
            return nil
        }
        
        let arrayOne = returnList(l1)
        let arrayTwo = returnList(l2)
        
        let mergeTwoArray = (arrayOne + arrayTwo).sorted(by : <)
        
        print(returnList(makeList(mergeTwoArray)))
        
        return makeList(mergeTwoArray)
    }
    
}

 

-- 설명 --

일단 두개의 연결리스트를 받게 됩니다.

그리고 만약에 둘다 없다면 nil을 한 쪽만 있다면 그 한쪽반 반환 하면 되죠!

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

 

그리고 리스트의 원소를 조회해서 배열로 만들어주는 returnList() 함수를 보도록 하겠습니다.

    func returnList(_ list : ListNode?) -> [Int]{
        
        var arrayList : [Int] = []
        
        guard var list = list else {
            return []
        }
        
        while true {
            
            arrayList.append(list.val)
            
            if let next = list.next {
                list = next
            }
            else{
                break
            }
    
        }
        
        return arrayList
    }

일단 arrayList를 생성해줍니다.

그리고 다음 노드가 nil이 아닐 때 까지 탐색을 해줍니다. nil이 아니라면 배열에 원소를 담아 주도록 합니다.

참고로!!!

while ( list != nil ) 한다면 ListNode 자체는 nil 아니기 때문에 항상 true 값을 반환하게 되므로 안되고

while ( list.next != nil ) 이라고 한다면 마지막 원소가 나오지 않게 됩니다.

왜냐하면 1 -> 2 -> 3 -> 4 라고 했을 때, 3에서 4로 이동하게 되면 4.next == nli 이 되기 때문에 4를 출력하지 않게 됩니다.

 

이제 makeList()를 보도록 하겠습니다.

 func makeList(_ arrayList : [Int]) -> ListNode? {
        
        var returnListNode : ListNode? = nil
        
        var next : ListNode? = nil
        
        for item in arrayList{
            
            if returnListNode == nil {
                returnListNode = ListNode(item)
                next = returnListNode!
            }
            else{
                next!.next = ListNode(item)
                next = next!.next
            }
            
        }
        
        return returnListNode ?? nil
        
    }

이 부분에서 많은 애를 먹었습니다.

        returnListNode = ListNode(1)
        returnListNode!.next = ListNode(2)
        let temp = returnListNode!.next
        temp!.next = ListNode(3)
        let temp2 = temp?.next
        temp2?.next = ListNode(4)

일단 이 코드를 이해할 필요가 있습니다.

returnListNode에 ListNode(1)을 생성해줍니다.  간단하게 1 이라고 표현하겠습니다.

1 -> nil 이 된 상태죠. 그리고 nil에 2를 넣게 되면 1 -> 2 -> Nil 입니다

그런데 temp라는 임시 변수에 2 -> nil 을 넣어 주게 됩니다. 처음에는 다른 변수의 주소 값을 가질 줄 알았습니다.

그러나 결국 returnListNode와 다 함께 연결이 되는 거 였습니다. 

즉, 연결리스트에서 새로운 값으로 이동 하기 위해서는 같은 주소를 공유하는 변수를 생성하고 거기에 값을 입력 해주면 

서로 연결 되는 거 였습니다.

 

결국 위에 코드도 마찮가지가 되는 겁니다. next.next에 새로운 ListNode를 생성해주고 next를 next.next로 이동 시켜주면 됩니다.

그런데 만약 returnList = returnList.next로 하게 된다면 계속 원본이 갱신되기 때문에 안됩니다.

꼭 새로운 변수를 생성해줘야합니다.

 

마지막으로 아래처럼 서로 배열을 묶어주고 오름차순으로 정렬을 해준다음 makeList()를 수행해주면 됩니다.

        let arrayOne = returnList(l1)
        let arrayTwo = returnList(l2)
        
        let mergeTwoArray = (arrayOne + arrayTwo).sorted(by : <)
        
        print(returnList(makeList(mergeTwoArray)))

 

swift로 연결 리스트를 구현하는게 쉬운 일은 아니였습니다.

처음 해보는 거라서, 많은 생각을 해봐야 해서 쪼끔 시간이 걸렸는데요.

좋은 경험이였습니다.

 

** 더 좋은 코드 **

    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
     
        guard let l1 = l1 else {return l2}
        guard let l2 = l2 else {return l1}
        var answer : ListNode? = nil
        
        if l1.val <= l2.val{
            answer = l1
            answer?.next = mergeTwoLists(l1.next, l2)
        }
        else {
            answer = l2
            answer?.next = mergeTwoLists(l1, l2.next)
        }
        
        return answer
        
    }

이것은 재귀함수를 사용해서 구현한 방법 입니다.

만약 숫자가 1 -> 3- > 4 와 1 -> 2 -> 5 로 구성 되어 있다면

처음 answer(1)는 1 -> 3 -> 4 를 받아 오게 됩니다. 

그리고 answert의 3 부분에 mergeTwoLists(3 -> 4 , 1-> 2-> 5) 이렇게 재귀를 보내게 됩니다.

그럼 answer(2)는 1 -> 2 -> 5 가 되고 answer(2)-> 2 부분에 mergeTwoList(3 -> 4 , 2 -> 5)가 들어가게 됩니다,

이런 식으로 들어가면  answer(1) = 1 -> answer(2) = 1 -> answer(3) = 2 -> answer(4) = 3 -> ,,,,

해서 마지막에 answer(1)이 반환이 됩니다.

결국 이와 같은 방식도 새로운 변수를 만들어 줘서 연결하는 방식이기 때문에

그 다음 주소값에 접속하기 위해서는 새로운 주소값을 만들어줘야하는거 잊지 마세욧!