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

举报
福大大架构师每日一题 发表于 2021/04/08 22:21:10 2021/04/08
【摘要】 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
}

执行结果如下:
在这里插入图片描述


左神java代码
评论

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200