2021-04-08:给定一个单链表的头节点head,请判断该链表是否为回文结构。
【摘要】 2021-04-08:给定一个单链表的头节点head,请判断该链表是否为回文结构。福大大 答案2021-04-08:1.找中点。2.按中点切分成两个链表。3.反转右边链表。4.相等判断。5.反转右边链表。6.左右链表合并。7.返回true或者false。代码用golang编写。代码如下:package mainimport "fmt"func main() { head := &Lis...
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
}
执行结果如下:
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)