请判断一个链表是否为回文链表。
如下 Go 实现的解法:
func isPalindrome(head *ListNode) bool {
s := []int{}
for ; head != nil; head = head.Next {
s = append(s, head.Val)
}
l := len(s)
for k, v := range s[:l/2] {
if v != s[l-1-k] {
return false
}
}
return true
}
空间复杂度:O(n),这种解法,我们使用了一个数组列表存放链表的元素值。n 指的是链表的元素个数。
进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
我们可以将链表的后半部分进行反转(修改链表结构),然后将前半部分和后半部分进行比较。比较完成后我们再将链表恢复原样。虽然不需要恢复也能通过测试用例。
整个流程可以分为以下五个步骤:
步骤 1 我们使用「快慢指针」在一次遍历中找到:慢指针一次走一步,快指针一次走两步,快慢指针同时出发。当快指针移动到链表的末尾时,慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
//找到前半部分链表的尾节点
endNode := end(head)
//翻转后半部分链表
fanNode := fan(endNode.Next)
//判断是否回文
n1 := head
n2 := fanNode
for n2 != nil {
if n1.Val != n2.Val {
return false
break
}
n1 = n1.Next
n2 = n2.Next
}
endNode.Next = fan(fanNode)
return true
}
func end (head *ListNode) *ListNode{
fast := head
slow := head
for fast.Next != nil && fast.Next.Next != nil {
fast = fast.Next.Next
slow = slow.Next
}
return slow
}
func fan(head *ListNode) *ListNode{
var pre, cur *ListNode = nil, head
for cur != nil {
tmpNode := cur.Next
cur.Next = pre
pre = cur
cur = tmpNode
}
return pre
}
「复杂度分析」