2021-04-08：給定一個(gè)單鏈表的頭節(jié)點(diǎn)head，請(qǐng)判斷該鏈表是否為回文結(jié)構(gòu)。

福大大 答案2021-04-08：

1.找中點(diǎn)。
2.按中點(diǎn)切分成兩個(gè)鏈表。
3.反轉(zhuǎn)右邊鏈表。
4.相等判斷。
5.反轉(zhuǎn)右邊鏈表。
6.左右鏈表合并。
7.返回true或者false。

代碼用golang編寫(xiě)。代碼如下：

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()
}

//獲取中點(diǎn)
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
}

//反轉(zhuǎn)鏈表
func Reverse(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    var next *ListNode
    for cur != nil {
        next = cur.Next
        cur.Next = pre
        //準(zhǔn)備下一次循環(huán)
        pre, cur = cur, next
    }
    return pre
}

func isPalindrome(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    //找中點(diǎn)
    mid := GetMid(head)
    //切斷成兩個(gè)鏈表
    rStart := mid.Next
    mid.Next = nil
    //反轉(zhuǎn)右邊鏈表
    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
    }

    //反轉(zhuǎn)右邊鏈表
    Reverse(rEnd)

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

    return ans
}

執(zhí)行結(jié)果如下：

在這里插入圖片描述

左神java代碼
評(píng)論