[Leetcode/Easy] 팰린드롬 연결 리스트 (234. Palindrome Linked List, Swift)

https://leetcode.com/problems/palindrome-linked-list/submissions/1312234161/

 

🤔 문제 설명

연결 리스트가 팰린드롬 구조인지 판별하라.
팰린드롬에 대한 설명은 2024.06.27 - [Algorithm] - [Leetcode/Easy] 유효한 팰린드롬 (125. Valid Palindrome, Swift) 글 참조

단, 노드 값의 범위는 다음과 같다. (0 <= ListNode.val <= 9)

head = [1,2,2,1]
// true

 

💡 풀이 1 : Linked List를 Array로 변환해서 풀기 

해당 문제는 입력값이 단일 연결 리스트(Singly-Linked List) 형태로 들어오기 때문에 Swift 문법에서 어떻게 사용하는지를 살펴봐야 한다.
연결 리스트(Linked List)란 데이터의 순서가 메모리에 물리적 순서대로 저장되지 않는 자료형으로 (배열과의 차이점),
실제로는 물리 메모리 어딘가에 흩뿌려진 노드 (Node)들이 서로 연결된 형태로 구성된 자료구조에 해당한다.

• ListNode = val (데이터 값) + next (다음 노드, 마지막 노드인 경우 연결된 노드가 nil일 수도 있으므로 옵셔널로 선언)
• init() : 값도 없고 다음 노드도 없는 최초 연결 리스트 생성 시 사용하는 생성자
• init(_val: Int) : 처음 연결 리스트에 최초값 할당 시 사용하는 생성자
• init(_val: Int, _ next: ListNode?) : 연결리스트에 값도 할당하고, 다음 Node도 연결하는 경우 사용하는 생성자

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

문제는 연결 리스트를 배열로 만들어서 기존 배열과 reversed된 배열이 같은지를 비교하면, 팰린드롬을 비교할 수 있을 것 같았다.

이때 연결 리스트를 배열로 바꿔준 이유는 "단일 연결 리스트 (Singly-Linked List)" 형태에서는 "뒤에서부터 앞으로 넘어갈 수 없다"는 특징 때문이라고 보면 되는데,
연결 리스트의 next 노드를 계속 추적해가면서 nil이 될 때까지 배열에 계속 append 해주면 이 문제를 해결할 수 있었다.

💡 Runtime : 362ms (Beats 59.24%), Memory : 21.88MB (Beats 63.03%)

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        var nodeArray = [Int]()
        guard var head else { return true }

        // Linked List -> Array 형태로 변경
        while (head.val != nil) {
            nodeArray.append(head.val)
            guard let next = head.next else { break }
            head = next
        }

        // Check Palindrome
        return nodeArray == nodeArray.reversed()
    }
}

 

💡 풀이 2 : Runner 기법을 사용한 풀이

연결 리스트를 우아하게 푸는 방법으로는 러너(Runner) 기법을 활용하는 풀이법도 있다.

한 번에 두 칸씩 이동하는 빠른 러너와, 한 번에 한 칸씩을 이동하는 느린 러너가 있다고 할 때, 빠른 러너가 연결 리스트 끝 부분에 도착하게 될 경우, 느린 러너는 연결 리스트에 절반 부분에 도착하게 된 것을 의미할거다.

이 점을 활용해서 느린 러너는 빠른 러너와 같이 이동할 때는 연결 리스트를 거꾸로 만들어나갈거다. ([1, 2, 3]이 있다고 하면 [3, 2, 1] 순으로 연결이 되도록)
그리고 빠른 러너가 도착을 했을 때는 fastRunner가 거꾸로 만든 연결 리스트와 앞으로 나가는 연결 리스트를 계속 비교해나가면서 다르면 바로 false를 리턴하도록! 끝까지 나갔는데도 같으면 true를 리턴하도록! 설정했다.

💡 Runtime : 332ms (Beats 47.39%), Memory : 22.72MB (Beats 18.48%)

class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {
        if (head == nil || head?.next == nil) { return true }

        var fastRunner = head       // 빠른 러너 (한번에 2칸씩 이동)
        var slowRunner = head       // 느린 러너 (한번에 1칸씩 이동)
        var rev: ListNode? = nil    // 반전된 리스트의 헤드

        while fastRunner != nil && fastRunner!.next != nil {
            fastRunner = fastRunner!.next!.next

            let nextSlow = slowRunner!.next
            slowRunner!.next = rev
            rev = slowRunner
            slowRunner = nextSlow
        }
        if (fastRunner != nil) { slowRunner = slowRunner!.next }  // 홀수 길이일 때는 한 칸 더!

        // 팰린드롬 비교
        while rev != nil && slowRunner != nil {
            if (rev!.val != slowRunner!.val) { return false }
            rev = rev!.next
            slowRunner = slowRunner!.next
        }

        return true
    }
}