2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。
福大大 答案2021-04-08：
1.找中点。
2.按中点切分成两个链表。
3.反转右边链表。
4.相等判断。
5.反转右边链表。
6.左右链表合并。
7.返回true或者false。
代码用golang编写。代码如下：
package mainimport "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}执行结果如下：
左神java代码
评论