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

题目描述

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

示例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)

• 编辑
• 预览