LeetCode - Algorithms - 234. Palindrome Linked List

Problem

234. Palindrome Linked List

Follow up

Could you do it in O(n) time and O(1) space?

Java

Break and reverse second half

© LeetCode – Palindrome Linked List (Java) - Java Solution 2 - Break and reverse second half

We can use a fast and slow pointer to get the center of the list, then reverse the second list and compare two sublists. The time is O(n) and space is 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true;

        //find list center
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode secondHead = slow.next;
        slow.next = null;

        //reverse second part of the list
        ListNode p1 = secondHead;
        ListNode p2 = p1.next;
        while (p1 != null && p2 != null) {
            ListNode temp = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = temp;
        }
        secondHead.next = null;

        //compare two sublists now
        ListNode p = (p2 == null ? p1 : p2);
        ListNode q = head;
        while (p != null) {
            if (p.val != q.val)
                return false;
            p = p.next;
            q = q.next;
        }
        return true;
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 1 ms, faster than 95.13% of Java online submissions for Palindrome Linked List.
  • Memory Usage: 41.7 MB, less than 5.11% of Java online submissions for Palindrome Linked List.

extrap space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        int n = list.size();
        for (int i = 0; i < n / 2; i++) {
            if (list.get(i).val != list.get(n - 1 - i).val)
                return false;
        }
        return true;
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 2 ms, faster than 39.06% of Java online submissions for Palindrome Linked List.
  • Memory Usage: 42.8 MB, less than 5.11% of Java online submissions for Palindrome Linked List.

Recursion

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null)
            return true;
        if (head.next == null)
            return true;
        ListNode secondLast = head;
        while (secondLast.next.next != null) {
            secondLast = secondLast.next;
        }
        if (head.val == secondLast.next.val) {
            secondLast.next = null;
            return isPalindrome(head.next);
        } else {
            return false;
        }
    }
}

Submission Detail

  • 26 / 26 test cases passed.
  • Runtime: 1406 ms, faster than 5.02% of Java online submissions for Palindrome Linked List.
  • Memory Usage: 42.7 MB, less than 5.11% of Java online submissions for Palindrome Linked List.