swift 리트코드 문제풀이 - leetcode 21 두 정렬 리스트의 병합

swift 리트코드 문제풀이 - leetcode 21 두 정렬 리스트의 병합

 

leetcode 21. Merge Two Sorted Lists

 

문제

아래 처럼 정렬이 되어 있는 두 연결 리스트를 합하라.

 

위의 그림에서 빨간색 연결리스트를 A 연결리스트라고 하고 보라색 연결 리스트를 B라고 해보자

리트코드 swift 답쓰기란을 보면 아래와 같은 함수가 주어진다.

아래 함수를 호출 할때 연결리스트 A와 연결 리스트 B를 인자로 전달하면 아래 함수는 두 A,B 연결리스트 안의 숫자들을 비교해서 오름차순으로 정렬한 새로운 연결리스트 C를 리턴해주면된다.

 

 func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? { 
 return
 }

 

일단 문제를 보자마자 든생각은 아래와 같다.

 

1.함수 안에 빈배열을 선언한다.

2.A연결리스트의 요소들을 while문을 돌면서 위에서 생성한 빈 배열에 넣는다.

3.B연결리스트의 요소들을 while문을 돌면서 위에서 생성한 빈 배열에 넣는다.

4.배열을 오름차순으로 sorting 한다.

5.배열안의 요소들을 이용해서 새로운 연결리스트 C를 생성한다.

문제풀이 과정

위의 순서대로 아래에 swift로 코드를 작성했다.

 

소스코드

//
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:CustomStringConvertible{
   public var description: String{
       guard let next = next else {
           return "\(val)"
       }
       return "\(val) -> " + String(describing: next) + " "
   }
}

    /// 14. 두 정렬 리스트의 병합
   func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
       var resultArray : [Int] = []
       
       //A연결리스트의 요소들을 배열에 담는다.
       var aList = l1
       while aList != nil{
           print("aList : \(aList?.val ?? 0)")
           resultArray.append(aList?.val ?? 0)
           aList = aList?.next
       }
       
       print("")
       
       //B연결 리스트의 요소들을 배열에 담는다.
       var bList = l2
       while bList != nil{
           print("bList : \(bList?.val ?? 0)")
           resultArray.append(bList?.val ?? 0)
           bList = bList?.next
       }
       
       print("resultArray : \(resultArray)")
       
       // 오름차순으로 정렬한다.
       resultArray = resultArray.sorted(by: <)
       print("resultSortedArray : \(resultArray)")
       print("length : \(resultArray.count)")
       
       // 배열안의 요소를 사용해서 새로운 연결리스트를 생선한다.
       let lastIndex = resultArray.count - 1
       var length = resultArray.count - 1
       var nextNode : ListNode? = nil
       while length >= 0{
           
           if length == lastIndex {
               nextNode = ListNode(resultArray[length])
           }else{
               let node = ListNode(resultArray[length] , nextNode)
               nextNode = node
           }
           length -= 1
       }
       print("nextNode : \(nextNode)")
       
       return nextNode
   }


   //A Linked List
let aListFour = ListNode(4)
let aListTwo = ListNode(2,aListFour)
let aListOne = ListNode(1,aListTwo)

print("aListOne : \(aListOne)")

   ///B Linked List
let bListFour = ListNode(4)
let bListThree = ListNode(3,bListFour)
let bListOne = ListNode(1,bListThree)

print("bLIstOne : \(bListOne)")

mergeTwoLists(aListOne,bListOne)

 

결과