题目

回文链表

问题:

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

进阶:

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