Swift) LeetCode(Easy) - Palindrome Linked List(Linked List)

leetcode.com/problems/palindrome-linked-list/

Palindrome Linked List - LeetCode

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

 

이번에는 연결 리스트로 펠린드롬 문제를 풀어 봤습니다...

역시 주소값을 다루는 건 직관적이지 않아서 어렵습니다 ㅠㅠ

 

총 두 가지의 방법으로 풀었고요.

처음에 푼 방법은 

    func isPalindrome2(_ head: ListNode?) -> Bool {
    
        guard var head = head else {return true}
        
        var list : [Int] = []
        
        while true {
            
            list.append(head.val)
            
            if head.next == nil {
                break
            }
              
            head = head.next!
            
        }
        
        var start = 0
        var end = list.count - 1
        
        while start < end {
            
            if list[start] != list[end]{
                return false
            }
            start += 1
            end -= 1
        }
        
        return true
    }

간단하게 새롭게 배열을 만들어서 배열의 상태에서 펠린드롬인지 아닌지 검사하는 방식 이였습니다.

쉽게 생각했죠. 그런데 연결리스트 문제인데, 배열 방식으로 풀어서 많이 마음에 들진 않았습니다

 

그래서 다른 방법으로 풀었습니다

    
    func isPalindrome(_ head: ListNode?) -> Bool {
    
        guard var head = head else {return true}
        
        guard let centerLocation : ListNode = getCenter(head) else {return true}
        
        var reversedListNode = reverseListNode(centerLocation)
        
        while reversedListNode != nil {
            
            if head.val != reversedListNode?.val {
                return false
            }
            
            head = head.next!
            reversedListNode = reversedListNode?.next
            
        }
        
        return true
        
    }
    
    func getCenter(_ head : ListNode) -> ListNode?{
        
        var moveSlow : ListNode? = head
        var moveSlowCnt = 0
        
        var moveFastCnt = 0
        var moveFast : ListNode? = head
        
        while moveFast != nil {
            
            moveFast = moveFast?.next?.next
            moveFastCnt += 2
            moveSlow = moveSlow?.next
            moveSlowCnt += 1
        }
        
        print(" 이동한 횟수 : \(moveSlowCnt) , \(moveFastCnt)")
        return moveSlow
    }
    
    func reverseListNode(_ head : ListNode?) -> ListNode?{
        
        var head = head
        
        var reversed : ListNode? = nil
        var new : ListNode? = nil
        while head != nil {
                
            if reversed == nil {
                reversed = ListNode(head!.val)
            }
            else{
                new = ListNode(head!.val)
                new?.next = reversed
                reversed = new
            }
            
            head = head?.next
        }
        
        return reversed
    }
    

아주 지저분 합니다.

하나씩 알아가보도록 하겠습니다.

 guard let centerLocation : ListNode = getCenter(head) else {return true}

====================================================================================

 func getCenter(_ head : ListNode) -> ListNode?{
        
        var moveSlow : ListNode? = head
        var moveSlowCnt = 0
        
        var moveFastCnt = 0
        var moveFast : ListNode? = head
        
        while moveFast != nil {
            
            moveFast = moveFast?.next?.next
            moveFastCnt += 2
            moveSlow = moveSlow?.next
            moveSlowCnt += 1
        }
        
        print(" 이동한 횟수 : \(moveSlowCnt) , \(moveFastCnt)")
        return moveSlow
    }

이 코드를 본다면 일단 getCenter는 중간 지점을 찾아 주는 함수 입니다.

getCenter함수를 보도록 하겠습니다.

이 함수를 본다면 moveSlow와 moveFast가 있습니다

moveSlow는 한칸씩 이동하고 moveFast는 두칸씩 이동하게 됩니다

그럼 어떻게 될까요?? moveFast가 moveSlow 보다 두배 빠르게 움직입니다. 그렇다면 moveSlow가 절반의 위치에 도달하면

moveFast는 두배 빠르니 두배 만큼 도착 했을 겁니다.

slow : fast = 1 : 1 -> 2 : 3 -> 3 : 5 -> 4 : 7 -> 5 : 9 -> 6 : 11 -> 7 : 13 -> 8 : 15 -> 9 : 17 ,,,,

이렇게 보면 거의 두배 정도 차이나는게 보이죠?

그런데 만약에 입력 값이 1 하나라면 바로 nil을 반환 해주게 되니, guard 로 풀어줍니다.

 

   func reverseListNode(_ head : ListNode?) -> ListNode?{
        
        var head = head
        
        var reversed : ListNode? = nil
        var new : ListNode? = nil
        while head != nil {
                
            if reversed == nil {
                reversed = ListNode(head!.val)
            }
            else{
                new = ListNode(head!.val)
                new?.next = reversed
                reversed = new
            }
            
            head = head?.next
        }
        
        return reversed
    }

reversedListNode는 연결리스트를 반대로 돌리는 겁니다.

head는 ListNode? 이기 때문에 nil이 가능합니다. 따라서 head가 nil 이 아닐때 까지 반복문을 돌려줍니다.

그리고 새로운 것을 만들어주고 그 새로운 녀석 뒤에 기존에 것들을 붙여주면 reverse가 구현이 됩니다.

 

펠린드롬 문제를 다뤄봤습니다.

어렵네요,,,,, 

그럼 모두 즐코코 하세요!