LeetCode - Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

Problems

Given a singly linked list, check if this linked list is palin or not

Solution

Firstly, we may need to split the linked list into 2 parts: the left part and the right part. We can archive this by using fast and slow pointers (slow go 1 step and fast go 2 steps).

Assume we have 2 parts of the given linked list, i have two solutions to check the given linked list is palin or not.

The first solution

We store the first parts of linked list into a stack. Then we can traverse through the second part of linked list, for each node, we pop the stack by one and compare the value. If we can reach into the end of the stack, then the given linked list is palin.

This solution has O(N) memory and O(N) time complexity

The second solution

We will reverse the first part of linked list, then we compare the reversed linked list and the second part. If these two linked list are the same, then the given linked list is palin.

This solution has O(1) memory and O(N) time complexity

Conclusion

So, which solution is the best solution? I don’t know, it depends. The second solution seems better since it only has O(1) memory complexity but it will change the given input. The first solution will keep the given input stay the same.

Code for the second solution

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
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func isPalindrome(head *ListNode) bool {
if head == nil || head.Next == nil {
// Base case, empty linked list or single element linked list
return true
}

// Finding the middle element of linked list
slow, fast := head, head
for fast.Next != nil && fast.Next.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}

// Split the linked list into 2 parts, reverse the second half then compare
second := slow.Next
first := head
second = reverse(second);

for second != nil && first != nil {
if second.Val != first.Val {
return false
}
second = second.Next
first = first.Next
}
return true
}

func reverse(head *ListNode) *ListNode {
var prev *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = prev
prev = cur
cur = next
}
return prev
}

Support me via: https://ko-fi.com/iamquang95