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é =))