题目

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

示例 1:

  1. 输入: 1->2
  2. 输出: false

示例 2:

输入: 1->2->2->1
输出: true

方案一（deque）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    // 使用切片
    list := make([]*ListNode, 0)
    node := head
    for node != nil {
        list = append(list, node)
        node = node.Next
    }

    for len(list) > 1 {
        first := list[0]
        last := list[len(list) - 1]
        if first.Val != last.Val {
            return false
        }
        list = list[1: len(list) - 1]
    }
    return true
}
  • 空间复杂度 回文链表 - 图1, 时间复杂度 回文链表 - 图2

其他的思路：

  1. 使用快慢指针（fast = 2 * slow），找到中间节点同时翻转前半部分链表，然后在进行比较。——时间复杂度 回文链表 - 图3 空间复杂度 回文链表 - 图4；
  2. 直接翻转链表，同时得到链表长度；然后比较翻转前后两个链表的前一半节点；

方案二（参考 leetcode 结果）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func isPalindrome(head *ListNode) bool {
    if head == nil {
        return true
    }

    var pre, half *ListNode
    slow, fast := head, head
    for fast.Next != nil {
        fast = fast.Next
        if fast.Next != nil { // 偶数个
            fast = fast.Next
            pre, slow, slow.Next = slow, slow.Next, pre
            half = slow.Next
        } else { // 奇数个
            pre, slow, slow.Next = slow, slow.Next, pre
            half = slow
        }
    }
    for half != nil{
        if half.Val != pre.Val {
            return false
        }
        half, pre = half.Next, pre.Next
    }
    return true
}

上述提到的其他思路中的第一种。

原文

https://leetcode-cn.com/explore/learn/card/linked-list/195/classic-problems/754/