拜托,面试别再问我回文链表了!!!(leetcode 234)

tomorrowwu · · 394 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

题目描述

请判断一个链表是否为回文链表。

示例1:

输入: 1->2
输出: false

示例2:

输入: 1->2->2->1
输出: true

进阶:

你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

解题思路

思路1

  • 遍历链表,用数组存下每个节点的值,然后从数组两头开始向中间遍历,是否相等
  • 时间复杂度O(n),空间复杂度O(n)

思路2

  • 遍历一遍链表,得到链表长度n,根据长度的奇偶,找到中间节点,将左半边的链表反转,然后从中间节点分两个方向向左右两边遍历,是否是回文;对左半部分链表进行反转,还原为最初的链表
  • 只需要固定的若干个临时变量,不需要额外开辟空间
  • 时间复杂度为O(n),空间复杂度为O(1)

代码实现

// ListNode Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// 解法1
// 用数组存前面的一半节点的值
// 时间复杂度:O(N)
// 空间复杂度:O(N)
func isPalindrome(head *ListNode) bool {
    // 空链表,算回文
    if head == nil {
        return true
    }

    var data []int
    for cur := head; cur != nil; cur = cur.Next {
        data = append(data, cur.Val)
    }

    for i, j := 0, len(data)-1; i <= j; {
        if data[i] != data[j] {
            return false
        }
        i++
        j--
    }
    return true
}

// 解法2
// 找到链表中间节点,将前半部分转置,再从中间向左右遍历对比
// 时间复杂度:O(N)
// 空间复杂度:O(1)
func isPalindrome2(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return true
    }
    isPalindrome := true

    //链表长度
    length := 0
    for cur := head; cur != nil; cur = cur.Next {
        length++
    }

    //将前半部分反转
    step := length / 2
    var prev *ListNode
    cur := head
    for i := 1; i <= step; i++ {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    mid := cur

    var left, right *ListNode = prev, nil
    if length%2 == 0 {
        //长度为偶数
        right = mid
    } else {
        right = mid.Next
    }

    //从中间向左右两边遍历对比
    for left != nil && right != nil {
        if left.Val != right.Val {
            //值不相等,不是回文链表
            isPalindrome = false
            break
        }
        left = left.Next
        right = right.Next
    }

    //将前半部分反转的链表进行复原
    cur = prev
    prev = mid
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }

    return isPalindrome
}

GitHub

  • 源码传送门
  • 项目中会提供各种数据结构及算法的Golang实现, LeetCode解题思路及答案
题目来源

leetcode 234. 回文链表


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:tomorrowwu

查看原文:拜托,面试别再问我回文链表了!!!(leetcode 234)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

394 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传