鏈表是通過“指針”將一組零散的內(nèi)存塊串聯(lián)使用诵次，內(nèi)存塊陳偉鏈表的結(jié)點(diǎn)薛夜，沒個(gè)鏈表的結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)速梗，還會(huì)使用后續(xù)指針next記錄鏈上的下一個(gè)結(jié)點(diǎn)肮塞。
鏈表的第一個(gè)結(jié)點(diǎn)叫作頭結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)叫作尾結(jié)點(diǎn)姻锁，頭結(jié)點(diǎn)記錄鏈表的基地址枕赵，而尾結(jié)點(diǎn)指向一個(gè)空地址NULL。
回文串是一個(gè)正讀和反讀都一樣的字符串位隶，比如“l(fā)evel”或者“noon”等等就是回文串拷窜。
判斷是否是回文字符串的步驟：
1.創(chuàng)建一個(gè)結(jié)點(diǎn)類（包含存儲(chǔ)的數(shù)據(jù)和next指針）：
class ListNode: NSObject {
var value:Any?
var next:ListNode?
init(value:Any?) {
self.value = value
}
}
2.將一個(gè)字符串轉(zhuǎn)換稱為一個(gè)單鏈表：
class LinkedList: NSObject {
var linkedList:ListNode?
// 初始化字符串為單鏈表
init(value:String?) {
if value == nil || value?.count == 0 {
return
}
let array = Array(value!)
for tempValue in array.reversed() {
if linkedList == nil {
linkedList = ListNode.init(value: tempValue)
linkedList?.next = nil
} else {
let tempModel = ListNode.init(value: tempValue)
tempModel.next = linkedList;
linkedList = tempModel;
}
}
}
}
3.判斷一個(gè)單鏈表存儲(chǔ)的字符串是否是回文：
// “回文串”是一個(gè)正讀和反讀都一樣的字符串，比如“l(fā)evel”或者“noon”等等就是回文串。
func isPalindrome(head:ListNode?) -> Bool {
if head == nil || head?.next == nil {
return true
}
var prev : ListNode? = nil
var slow : ListNode? = head
var fast : ListNode? = head
// 處理前面半截字符串的反轉(zhuǎn) 和后半截字符串的截取
while fast != nil && fast?.next != nil {
fast = fast?.next?.next ?? nil
let next = slow?.next
slow?.next = prev
prev = slow
slow = next
}
//當(dāng)為奇數(shù)位字符串的時(shí)候fast不為空 說明后半截多了一個(gè)中間的字符 所以需要等于next
if fast != nil {
slow = slow?.next
}
// 比較字符串是否一致
while slow != nil {
if (slow?.value as! Character) != (prev?.value as! Character) {
return false
}
slow = slow?.next
prev = prev?.next
}
return true
}
空間復(fù)雜度為O(1),時(shí)間復(fù)雜度為O(n)
參考java單鏈表存儲(chǔ)的回文串
