题目

回文链表

问题:

请判断一个链表能否为回文链表。

进阶:

你是否用 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    }