forked from neetcode-gh/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0234-palindrome-linked-list.go
48 lines (42 loc) · 910 Bytes
/
0234-palindrome-linked-list.go
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
/**
Move slow and fast pointer along the list.
Slow pointer nodes are added to reversed list.
When no more fast move is possible, iterate
along slow and back along reversed list while
checking for value equality
Time: O(N)
Space: O(1)
**/
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
slow, fast := head, head
var rev *ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
next_slow := slow.Next
slow.Next = rev
rev = slow
slow = next_slow
}
// if fast is not null, slow is middle of
// odd length list which is skipped
// if fast is null, slow is first element of
// the 2nd half of even length list
if fast != nil {
slow = slow.Next
}
for slow != nil {
if slow.Val != rev.Val {
return false
}
slow = slow.Next
rev = rev.Next
}
return true
}