題目描述
請(qǐng)判斷一個(gè)鏈表是否為回文鏈表疚膊。
示例1:
輸入: 1->2
輸出: false
示例2:
輸入: 1->2->2->1
輸出: true
進(jìn)階:
你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題料扰？
解題思路
思路1
- 遍歷鏈表,用數(shù)組存下每個(gè)節(jié)點(diǎn)的值,然后從數(shù)組兩頭開(kāi)始向中間遍歷,是否相等
- 時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(n)
思路2
- 遍歷一遍鏈表,得到鏈表長(zhǎng)度n,根據(jù)長(zhǎng)度的奇偶,找到中間節(jié)點(diǎn),將左半邊的鏈表反轉(zhuǎn),然后從中間節(jié)點(diǎn)分兩個(gè)方向向左右兩邊遍歷,是否是回文;對(duì)左半部分鏈表進(jìn)行反轉(zhuǎn),還原為最初的鏈表
- 只需要固定的若干個(gè)臨時(shí)變量,不需要額外開(kāi)辟空間
- 時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(1)
代碼實(shí)現(xiàn)
// ListNode Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// 解法1
// 用數(shù)組存前面的一半節(jié)點(diǎn)的值
// 時(shí)間復(fù)雜度：O(N)
// 空間復(fù)雜度：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
// 找到鏈表中間節(jié)點(diǎn)锌蓄，將前半部分轉(zhuǎn)置熬尺，再?gòu)闹虚g向左右遍歷對(duì)比
// 時(shí)間復(fù)雜度：O(N)
// 空間復(fù)雜度：O(1)
func isPalindrome2(head *ListNode) bool {
if head == nil || head.Next == nil {
return true
}
isPalindrome := true
//鏈表長(zhǎng)度
length := 0
for cur := head; cur != nil; cur = cur.Next {
length++
}
//將前半部分反轉(zhuǎn)
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 {
//長(zhǎng)度為偶數(shù)
right = mid
} else {
right = mid.Next
}
//從中間向左右兩邊遍歷對(duì)比
for left != nil && right != nil {
if left.Val != right.Val {
//值不相等,不是回文鏈表
isPalindrome = false
break
}
left = left.Next
right = right.Next
}
//將前半部分反轉(zhuǎn)的鏈表進(jìn)行復(fù)原
cur = prev
prev = mid
for cur != nil {
cur.Next, prev, cur = prev, cur, cur.Next
}
return isPalindrome
}
GitHub
- 源碼傳送門(mén)
- 項(xiàng)目中會(huì)提供各種數(shù)據(jù)結(jié)構(gòu)及算法的Golang實(shí)現(xiàn), LeetCode解題思路及答案
