HàPhan 河

Palindrome Linked List (P.95 - CtCI)

Giải bài 2.6 trang 95 sách Cracking the Coding Interview 6th. Edition.

Palindrome: Implement a function to check if a linked list is a palindrome.

Level: Easy

Trước tiên cần hiểu Palindrome là gì.

a word, phrase, or sequence that reads the same backward as forward, e.g., madam or nurses run.

đó Google translate đó =)).

Một chuỗi, một danh sách đi ngược đi xuôi đều giống nhau. Ví dụ:
abc, kappak, 12321, [5,5,5,5], [5,4,2,4,5], [""].

Thông thường sẽ làm việc với array nhưng hôm nay bài toán mình sẽ giải với danh sách liên kết. Ví dụ
a -> b -> c -> b -> a -> nil : return true
a -> nil : return true
a -> b -> nil : return false

Corner case:
nil : return true

Okay. Phân tích một chút nhỉ.
Đối với array, chúng ta chỉ cần cho 2 index chạy từ 2 đầu là có thể giải quyết với O(n) time và O(1) space. Còn với danh sách liên kết, vì chỉ biết node đầu tiên nên không thể dùng cách giải quyết ở trên để giải quyết được.

BCR: O(n)
Brute Force: O(n^2)

Cách tiếp cận: lộn ngược linked list, sau đó so sánh từng phần tử ban đầu.
Lộn ngược linked list tốn O(n) time, so sánh thêm O(n) nữa, tổng O(n + n) = O(2n) = O(n)
Cài đặt thử xem coi có optimize được gì không nhé.

class ListNode<T> {
    let val: T
    var next: ListNode<T>?
    
    init(_ val: T){
        self.val = val
    }
}
func reverse(_ root: ListNode<Int>?) -> ListNode<Int>? {
    var curNode : ListNode<Int>? = root
    var prevNode: ListNode<Int>? = nil
    
    while curNode != nil {
        let temp = curNode?.next
        curNode?.next = prevNode
        prevNode = curNode
        curNode = temp
    }
    
    return prevNode
}

Ở đây mình không làm việc với LinkedList mà mình chỉ làm việc với root node.

Mình viết một class util để visualize linked list

@discardableResult
func stringRepresent(_ root: ListNode<Int>?) -> String{
    var iterate = root
    var toPrint = ""
    while iterate != nil {
        toPrint.append(" \(iterate!.val) ->")
        iterate = iterate?.next
    }
    toPrint.append(" nil")
    return toPrint
}

Cách cài đặt chuối =))

func isPalindrome(_ root: ListNode<Int>?) -> Bool {
    let represent = stringRepresent(root) //O(n) time
    let afterReverse = stringRepresent(reverse(root)) //O(n) time
    return represent == afterReverse
}

Hàm reverse(_:) tốn O(n) time , đạt BCR, nhưng trong isPalindrome(_:) tốn thêm O(n) space.
Cho nên cần suy nghĩ lại cách cải thiện space.

30 phút suy nghĩ =))

func isEqual(_ left: ListNode<Int>?, _ right: ListNode<Int>?) -> Bool {
    var it1 = left
    var it2 = right
    
    while (it1?.val == it2?.val) {
        it1 = it1?.next
        it2 = it2?.next
    
        if it1 == nil && it2 == nil {
            return true
        }
    }
    
    return false
}

.
.
.
.
.
ra ra ra rồi =))
chúng ta không reverse toàn bộ linked list mà chỉ reverse nửa sau, sau đó so sánh với nửa đầu bằng method ở trên.
ví dụ:
1 -> 2 -> 3 -> 2 -> 1, cắt ra làm 2
first half: 1 -> 2 -> 3
second half: 3 -> 2 -> 1 // reverse cái này thành 1 -> 2 -> 3 ... xong.

Tại sao lại optimize hơn cái reverse nguyên list ở trên?
Vì reverse không tốn extra space, tìm node giữa cũng không tốn extra space (sẽ viết chi tiết ở một bài khác), tóm lại là không cần thêm space, chỉ thực hiện đổi mấy cái next là xong.
À hàm so sánh cũng không tốn extra space.

Một câu hỏi đặt ra là tại sao không so sánh cái reversed luôn mà còn bày trò =))
Vì: sau khi reverse toàn bộ thì cái root ban đầu chỉ next đến nil, muốn so sánh chính xác thì phải tạo bản clone cái danh sách trước rồi mới reverse. -> O(n) space.

Cài đặt xem nào:

func halfBreakList(_ root: ListNode<Int>?) -> (ListNode<Int>?, ListNode<Int>?) {
    var slowNode = root
    var fastNode = root?.next
    var beforSlow = root
    
    var length = 0
    while fastNode != nil {
        beforSlow = slowNode
        slowNode = slowNode?.next
        
        if fastNode?.next != nil {
            if fastNode?.next?.next != nil {
                length += 2
            }else {
                length += 1
            }
        }
        
        fastNode = fastNode?.next?.next
    }
    
    //danh sách chẵn phần tử thì đổi cái next thôi
    if length % 2 == 0{
        beforSlow?.next = nil
    }else {
        if slowNode != nil {
            let new = ListNode(slowNode!.val)
            beforSlow?.next = new
        }
    }
    
    return (root, slowNode)
}

Cái kỹ thuật 2 con trỏ nhanh chậm này có miêu tả trong sách The"Runner"Technique, một cái chạy trước k phần thử - k có thể sinh ra từ phép +, phép *...

Tada...simple but effective

func isPalindrome(_ root: ListNode<Int>?) -> Bool {
    let breaked = halfBreakList(root)
    let reversed = reverse(breaked.1)
    return isEqual(breaked.0, reversed)
}

Nhớ test cái corner case nhỉ.
https://leetcode.com/problems/palindrome-linked-list/

Qua bài này là có thể nắm được cả 2 kỹ thuật: lật ngược linked list, slow/fast node.

Xong linked list nhoé =))

Comments