[Go版]算法通关村第一关白银——判断是否回文链表

题目：判断是否是回文链表

题目链接：LeetCode-234. 回文链表

解决方法：快慢指针+递归反转链表

思路分析

1. 使用快慢指针，当快指针到达结尾停下时，慢指针正好在中间（注意：奇数链表时，慢指针在正中间；偶数链表时，慢指针在中间的下一位）
2. 然后反转此时的慢指针链表（比如：1->2->3->2->1，反转3->2->1，得到1(注意这个1是原链表的尾节点指针)->2->3）
3. 最后循环反转后的链表和原链表，依次取出首节点对比，值不等说明不是回文序列，直达循环结束，结束条件是反转链表遍历完，如果到结束都是相等的，说明就是回文序列

复杂度：时间复杂度: O ( n ) O(n) O(n)、空间复杂度: O ( 1 ) O(1) O(1)

• 时间复杂度: O ( n ) O(n) O(n)

  isPalindrome 函数的时间复杂度是 O ( n ) O(n) O(n)，其中 n 是输入链表中节点的个数。这是因为该函数首先使用快慢指针技巧找到链表的中间节点，这需要 O ( n / 2 ) O(n/2) O(n/2) 的时间。然后，它递归地反转链表的后半部分，这也需要 O ( n / 2 ) O(n/2) O(n/2) 的时间。最后，它比较原始链表和反转链表中每个节点的值，这需要 O ( n ) O(n) O(n) 的时间。总的时间复杂度为 O ( n / 2 ) O(n/2) O(n/2)+ O ( n / 2 ) O(n/2) O(n/2)+ O ( n ) O(n) O(n)= O ( n ) O(n) O(n)。

• 空间复杂度: O ( 1 ) O(1) O(1)

  isPalindrome 函数的空间复杂度是 O ( 1 ) O(1) O(1)，因为它仅使用常量级别的额外空间来存储变量和指针，与输入链表的大小无关。递归的 reverselist 函数在进行递归过程中只存储临时变量，不使用与输入规模成比例的额外数据结构。因此，空间复杂度为 O ( 1 ) O(1) O(1)。

Go代码

import (
    "fmt"
)
type ListNode struct {
	Val int
	Next *ListNode
}
func reverselist(head *ListNode) *ListNode {
    fmt.Println("reverse:", head.Val)
    if head == nil || head.Next == nil {
        return head
    }
    tmp := head
    newHead := reverselist(tmp.Next)
    tmp.Next.Next = tmp
    tmp.Next = nil
    return newHead
}
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return false
    }
    if head.Next == nil {
        return true
    }
    slow := head
    fast := head
    var newList *ListNode
    for {
        if fast == nil || fast.Next == nil{
            break
        }
        slow = slow.Next
        fast = fast.Next.Next
    }
    newList = reverselist(slow)
    isSame := true
    for {
        if newList == nil || head == nil {
            break
        }
        if newList.Val != head.Val {
            isSame = false
            break
        }
        newList = newList.Next
        head = head.Next
    }
    return isSame
}