Reference: LeetCode
Difficulty: EasyTwo Pointers

My Post: Java Solution Using Two Pointers, Half Reverse (easy-understand)

Problem

Given a singly linked list, determine if it is a palindrome.

Example:

1
2
3
4
5
6
7
8
Input: 1->2
Output: false

Input: 1->2->2->1
Output: true

Input: 1->2->3->2->1
Output: true

Follow up: Could you do it in $O(n)$ time and $O(1)$ space?

Analysis

Reverse Whole

Reverse the whole list and compare each element, but reversal should be non-destructive because we need to do comparison later.

Note: Non-destructive reversing can be tricky at the first glance.

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
public boolean isPalindrome(ListNode head) {
ListNode newHead = reverseNew(head);
ListNode p1 = head;
ListNode p2 = newHead;
while (p1 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}

// iteration
private ListNode reverseNew(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = null;
ListNode p = head;
// dummy 1 2 3 4
// p
while (p != null) { // addFirst
ListNode newNode = new ListNode(p.val);
newNode.next = dummy.next;
dummy.next = newNode;
p = p.next;
}
return dummy.next;
}

Time: $O(N)$
Space: $O(N)$

Reverse Half

The idea is to reverse the right half of the original list and then compare half elements. The difficulties lie in:

  • Handle even and odd cases.
  • How to get the right half.
1
2
3
4
5
6
7
8
9
// even
1 -> 2 -> 3 -> 4
left half: 1 -> 2
right half: 3 -> 4

// odd
1 -> 2 -> 3 -> 4 -> 5
left half: 1 -> 2
right half: 4 -> 5

To get the right half, we have two ways: Traversal based on the length, Slow-fast pointers. Here we use the slow-fast pointers to find the middle point.

In the examples above, which nodes do we want as heads of the right half? 3 (even case) and 4 (odd case).

So we can find the left-leaning middle point 2 and the exact middle point 3 by slow-fast pointers. Finally, returns their the next node.

In terms of left-leaning and right-leaning, check out the code and examples to get an intuition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private ListNode getRightHalf(ListNode head) {
if (head == null) return null;
ListNode slow = head;
ListNode fast = head.next; // left-leaning
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.next; // important!
}

private ListNode getRightHalf(ListNode head) {
if (head == null) return null;
ListNode slow = head;
ListNode fast = head; // right-leaning
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow.next; // important!
}

In the code, the difference is in the initializations of fast.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// left-leaning
1 -> 2 -> 3 -> 4
s s
f f
1 -> 2 -> 3 -> 4 -> 5
s s s
f f f
// right-leaning
1 -> 2 -> 3 -> 4
s s s
f f f
1 -> 2 -> 3 -> 4 -> 5
s s s
f f f

By observation, we want to use left-leaning in this case because slow could finally stop at the left-leaning middle point.

Here is the code:

1
2
3
4
5
6
7
8
9
10
public boolean isPalindrome(ListNode head) {
ListNode p1 = head;
ListNode p2 = reverse(getRightHalf(head));
while (p2 != null) {
if (p1.val != p2.val) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}

Note: We use p2 instead of p1 as our while-condition because p1 actually points to the list of all elements (reverse and getRightHalf do not disconnect the list). For example:

1
2
3
4
5
Example: 1 -> 2 -> 3 -> 4 -> 5
// After reversal() and getRightHalf()
p1 (left half): 1 -> 2 -> 5 -> 4 -> 3
p2 (right half): 5 -> 4 (although 5 is linked by 2)
// We only care about the first two nodes in each list.

The remaining helper function reverse():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// iteration
private ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = head;
ListNode prev = null;
while (p != null) {
ListNode nextTemp = p.next;
p.next = prev;
prev = p;
p = nextTemp;
}
return prev;
}

Time: $O(N)$
Space: $O(1)$ if not using recursion.


Comment