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.