·
·
文章目录
  1. 题目介绍
  2. 复杂度
  3. 解题思路

Palindrome Linked List

题目介绍

LeetCode 234. Palindrome Linked List

复杂度

时间复杂度: O(n), 空间复杂度: O(1)

解题思路

这一题思路比较多,比如赋值到数组里面在去进行判断,要满足 O(1) 的空间复杂度,需要考虑下。

大概分为三个函数:

  • 使用快慢指针找到链表的中间节点(第一次看到这个用途,很巧妙);
  • 使用反转链表函数反转后半部分链表;
  • 进行比较并将后半部分链表反转回去,保证原链表的完整性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
public class ListNode {
public var val: Int
public var next: ListNode?
public init(_ val: Int) {
self.val = val
self.next = nil
}
}

class Solution {
func isPalindrome(_ head: ListNode?) -> Bool {
let middle = endOfFirstHalf(head)
var first = head
var second = reverseList(middle?.next)
while(second != nil) {
if first?.val != second?.val {
reverseList(middle?.next)
return false
}
first = first?.next
second = second?.next
}
reverseList(middle?.next)
return true
}

@discardableResult
func reverseList(_ head: ListNode?) -> ListNode? {
var pre: ListNode? = nil
var cur = head
while(cur != nil) {
let t = cur?.next
cur?.next = pre
pre = cur
cur = t
}
return pre
}

func endOfFirstHalf(_ head: ListNode?) -> ListNode? {
var fast = head
var slow = head
while(slow?.next != nil && fast?.next?.next != nil) {
fast = fast?.next?.next
slow = slow?.next
}
return slow
}
}
**版权声明**

Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2020/03/13/PalindromeLinkedList/

支持一下
扫一扫,支持yeziahehe
  • 微信扫一扫
  • 支付宝扫一扫