题目
回文链表
问题:
请判断一个链表是否为回文链表。
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
示例:
示例 1：
输入: 1->2
输出: false
示例 2：
输入: 1->2->2->1
输出: true
解题思路:
我们首先想到的思路是通过建立一个list，然后将链表中的数存进去，然后判断这个list是否回文。但是这样做的空间复杂度是O(n)，显然无法满足空间复杂度O(1)的需求。我们可以建立快慢指针，通过这两个指针获得两个列表，
代码：
/**
public class SingNode {
public var value : Int
public var nextNode: SingNode?
public init(value:Int) {
self.value = value
}
}
extension SingNode : CustomStringConvertible {
public var description: String {
var string = "\(value)"
var node = self.nextNode
while node != nil {
string = string + " -- " + "\(node!.value)"
node = node?.nextNode
}
return string
}
}
**/
func isPalindrome(_ l1:SingNode?) -> Bool {
if l1 == nil || l1?.nextNode == nil {
return false
}
var fast = l1
var slow = l1
var nodeArr:[Int] = [Int]()
nodeArr.append(l1!.value)
while fast?.nextNode != nil && fast?.nextNode?.nextNode != nil {
slow = slow?.nextNode
fast = fast?.nextNode?.nextNode
nodeArr.append(slow!.value)
}
while slow?.nextNode != nil {
if nodeArr.count != 0 {
if nodeArr.removeLast() != slow?.nextNode?.value {
return false
}
} else {
return false
}
slow = slow?.nextNode
}
return true
}
