Leetcode: Palindrome Linked List, 연결 리스트 회문판별

문제설명

• 단일 연결리스트의 원소가 회문인지 판별하라
• 시간복잡도가 O(n)이면서 공간복잡도가 O(1)인 코드를 작성할 수 있다.

문제풀이

• 리스트의 중간 지점부터 끝까지 리스트를 거꾸로 만든다.
• 거꾸로 만든 리스트와 원본 리스트의 첫 번째부터 중간 지점까지 값이 같은지 판별한다.
• 리스트의 중간 지점을 찾아가기 위해, 연결리스트의 투 포인터 방법을 사용한다.

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
    }
}

func isPalindrome(_ head: ListNode?) -> Bool {
    if head == nil {
        return true
    }
    var first = head

    var reversed = reverseList(getMiddle(head))
    var result = true

    while let secondHalf = reversed, let firstHalf = first {
        if (secondHalf.val != firstHalf.val) {
            result = false
        }
        reversed = secondHalf.next
        first = firstHalf.next
    }
    return result
}

func reverseList(_ head: ListNode?) -> ListNode? {
    var before: ListNode? = nil
    var n = head
    while let node = n {
        let nextNode = node.next
        node.next = before
        before = n
        n = nextNode
    }
    return before
}
func getMiddle(_ node: ListNode?) ->  ListNode? {
    var fast = node
    var slow = node
    while let fastNode = fast, let slowNode = slow {
        fast = fastNode.next?.next
        slow = slowNode.next
    }

    return slow
}

//print(getMiddle(ListNode.from(arr: [1,2,3,4,5]))?.strings()) // 4->5
//print(getMiddle(ListNode.from(arr: [1,2,3,4]))?.strings()) // 3->4
//print(reverseList(ListNode.from(arr: [1,2,3,4,5]))?.strings()) // 5->4->3->2->1
print(isPalindrome(ListNode.from(arr: [1,2,3,4,5]))) // false
print(isPalindrome(ListNode.from(arr: [5,4,3,4,5]))) // true
print(isPalindrome(ListNode.from(arr: [5,5]))) // true
print(isPalindrome(ListNode.from(arr: [5]))) // true
print(isPalindrome(ListNode.from(arr: [4,5]))) // false
print(isPalindrome(ListNode.from(arr: [1,2,2,1]))) // true