2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。
原创2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。
原创
福大大架构师每日一题
修改于 2021-04-09 10:04:48
修改于 2021-04-09 10:04:48
2021-04-08：给定一个单链表的头节点head，请判断该链表是否为回文结构。
福大大 答案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
}执行结果如下：
在这里插入图片描述
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读