• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

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

互联网 diligentman 2周前 (04-08) 7次浏览

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
}

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


左神java代码
评论

展开阅读全文

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

2021-01-06:mysql中,我存十亿个手机号码,考虑存储空间和查询效率,用什么类型的字段去存?
2020-12-12:现场写代码,把CPU打满,java和go都行,并解释为什么。
2021-01-19:mysql中,一张表里有3亿数据,未分表,其中一个字段是企业类型,企业类型是一般企业和个体户,个体户的数据量差不多占50%,根据条件把个体户的行都删掉。请问如何操作?
2021-03-05:go中,io密集型的应用,比如有很多文件io,磁盘io,网络io,调大GOMAXPROCS,会不会对性能有帮助?为什么?


喜欢 (0)