[LeetCode] Problem 234 - Palindrome Linked List

Posted on | In ,

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

Example

No.1

Input: 1->2

Output: false

No.2

Input: 1->2->2->1

Output: true

Follow up

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

Code

1
2
3
4
5
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
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
public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null)
        return true;
    
    ListNode middle = findMiddle(head);
    middle.next = reverse(middle.next);

    ListNode node1 = head;
    ListNode node2 = middle.next;

    while (node1 != null && node2 != null) {
        if (node1.val != node2.val)
            return false;
        
        node1 = node1.next;
        node2 = node2.next;
    }

    return true;
}

private ListNode findMiddle(ListNode head) {
    ListNode slow = head;
    ListNode fast = slow.next;

    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

private ListNode reverse(ListNode current) {
    ListNode prev = null;
    
    while (current != null) {
        ListNode next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}