[LeetCode] 234. Palindrome Linked List / Swift

[문제 보기]

Given the head of a singly linked list, return true if it is a palindrome.

 

Example 1:

Input: head = [1,2,2,1] Output: true

Example 2:

Input: head = [1,2] Output: false

 

Constraints:

• The number of nodes in the list is in the range [1, 10^5].
• 0 <= Node.val <= 9

 

Follow up: Could you do it in O(n) time and O(1) space?

 

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

Palindrome Linked List - LeetCode

 

---

단방향 연결리스트의 회문 확인 문제였다.

내가 구현한 방법은 O(n)만큼 추가 공간을 사용한다.

follow up에서의 O(1)의 공간효율성을 위해서는 처음부터 절반까지부분의 연결리스트를 거꾸로 뒤집어야 했다.

 

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    func isPalindrome(_ head: ListNode?) -> Bool {       
        var rear = head
        var front = head?.next
        var stack = [head!]
        while front != nil {
            front = front?.next
            if front == nil {   // 마지막 노드일때고 짝수개
                rear = rear?.next
                break
            }
            front = front?.next
            if front == nil {    // 마지막 노드일때고 홀수개
                rear = rear?.next?.next
                break
            }
            rear = rear?.next
            stack.append(rear!)
        }
        while !stack.isEmpty {
            let last = stack.removeLast()
            if rear!.val != last.val {
                return false
            }
            rear = rear?.next
        }
        return true
    }
}

 

⭐️단방향 연결리스트를 뒤집는 로직

// 뒤집는 부분만 추가한 코드
var cur = head
var pre: ListNode? = nil // 현재노드의 next를 저장하기 위해 사용되는 변수
while cur != nil {
    // 뒤집는 핵심부분
    let temp = cur?.next
    cur?.next = pre
    pre = cur
    cur = temp
}