2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。

福大大架构师每日一题 · · 480 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

福大大答案2021-04-08：

1.找中点。
2.按中点切分成两个链表。
3.反转右边链表。
4.相等判断。
5.反转右边链表。
6.左右链表合并。
7.返回true或者false。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    head := &ListNode{Val: 1}
    head.Next = &ListNode{Val: 2}
    head.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next = &ListNode{Val: 3}
    head.Next.Next.Next.Next = &ListNode{Val: 2}
    head.Next.Next.Next.Next.Next = &ListNode{Val: 1}
    printlnLinkNodeList(head)
    ret := isPalindrome(head)
    printlnLinkNodeList(head)
    fmt.Println(ret)
}

//Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

//链表打印
func printlnLinkNodeList(head *ListNode) {
    cur := head
    for cur != nil {
        fmt.Print(cur.Val, "\t")
        cur = cur.Next
    }
    fmt.Println()
}

//获取中点
func GetMid(head *ListNode) *ListNode {
    fast := head
    slow := head
    if fast.Next != nil && fast.Next.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
    }
    return slow
}

//反转链表
func Reverse(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    var next *ListNode
    for cur != nil {
        next = cur.Next
        cur.Next = pre
        //准备下一次循环
        pre, cur = cur, next
    }
    return pre
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    //找中点
    mid := GetMid(head)
    //切断成两个链表
    rStart := mid.Next
    mid.Next = nil
    //反转右边链表
    rEnd := Reverse(rStart)
    //相等判断
    n1 := head
    n2 := rEnd
    ans := true
    for n1 != nil && n2 != nil {
        if n1.Val != n2.Val {
            ans = false
            break
        }
        n1, n2 = n1.Next, n2.Next
    }

    //反转右边链表
    Reverse(rEnd)

    //左右链表合并
    mid.Next = rStart

    return ans
}

执行结果如下：