234. Palindrome Linked List


Problem Description

The problem presents a scenario where you're given a singly linked list and asks you to determine if it is a palindrome. A palindrome is a sequence that reads the same forward and backward. For example, in the case of a linked list, [1 -> 2 -> 2 -> 1] is a palindrome, but [1 -> 2 -> 3] is not.

Intuition

To solve the problem of determining whether a linked list is a palindrome, we need an approach that allows us to compare elements from the start and end of the list efficiently. Since we can't access the elements of a linked list in a reverse order as easily as we can with an array, we have to be creative.

The solution involves several steps:

  1. Find the middle of the linked list: We can find the middle of the linked list using the fast and slow pointer technique. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be in the middle.

  2. Reverse the second half of the linked list: Starting from the middle of the list, reverse the order of the nodes. This will allow us to directly compare the nodes from the start and the end of the list without needing to store additional data or indices.

  3. Compare the first and the second half: After reversal, we then compare the node values from the start of the list and the start of the reversed second half. If all corresponding nodes are equal, then the list is a palindrome.

  4. Restore the list (optional): If the problem required you to maintain the original structure of the list after checking for a palindrome, you would follow up by reversing the second half of the list again and reattaching it to the first half. However, this step is not implemented in the provided code, as it is not part of the problem's requirements.

The crux of this approach lies in the efficient O(n) traversal and no additional space complexity apart from a few pointers, which makes this method quite optimal.

Solution Approach

The solution approach follows the intuition which is broken down into the following algorithms and patterns:

  1. Two-pointer technique: To find the middle of the list, we use two pointers (slow and fast). The slow pointer is incremented by one node, while the fast pointer is incremented by two nodes on each iteration. When the fast pointer reaches the end, slow will be pointing at the middle node.

    1slow, fast = head, head.next
    2while fast and fast.next:
    3    slow, fast = slow.next, fast.next.next
  2. Reversing the second half of the list: Once we have the middle node, we reverse the second half of the list starting from slow.next. To do this, we initialize two pointers pre (to keep track of the previous node) and cur (the current node). We then iterate until cur is not None, each time setting cur.next to pre, effectively reversing the links between the nodes.

    1pre, cur = None, slow.next
    2while cur:
    3    t = cur.next
    4    cur.next = pre
    5    pre, cur = cur, t
  3. Comparison of two halves: After reversing the second half, pre will point to the head of the reversed second half. We compare the values of the nodes starting from head and pre. If at any point the values differ, we return False indicating that the list is not a palindrome. Otherwise, we keep advancing both pointers until pre is None. If we successfully reach the end of both halves without mismatches, the list is a palindrome, so we return True.

    1while pre:
    2    if pre.val != head.val:
    3        return False
    4    pre, head = pre.next, head.next
    5return True

The code uses the two-pointer technique and the reversal of a linked list to solve the problem very effectively. The total time complexity of the algorithm is O(n), and the space complexity is O(1), because no additional space is used proportional to the input size; we're just manipulating the existing nodes in the linked list.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example. Consider the linked list [1 -> 2 -> 3 -> 2 -> 1]. The goal is to determine if this list represents a palindrome.

Step 1: Finding the Middle

We use the two-pointer technique. Initially, both slow and fast point to the first element, with fast moving to the next immediately for comparison purposes.

1Initial state:
2slow -> 1
3fast -> 2
4List: 1 -> 2 -> 3 -> 2 -> 1

Now we begin traversal:

1Iteration 1:
2slow -> 2
3fast -> 3
4List: 1 -> 2 -> 3 -> 2 -> 1
5
6Iteration 2:
7slow -> 3
8fast -> 1 (fast reaches the end of the list so we stop here)
9List: 1 -> 2 -> 3 -> 2 -> 1

At this stage, slow is pointing to the middle of the list.

Step 2: Reverse the Second Half

Starting from the middle node (where slow is currently pointing), we proceed to reverse the second half of the list. We'll use two pointers pre and cur to achieve this:

1pre points to None
2cur points to 3 (slow.next)
3List: 1 -> 2 -> 3 -> 2 -> 1

We now iterate and reverse the link between the nodes until cur is None:

1Iteration 1:
2pre -> 3
3cur -> 2
4Reversed part: None <- 3 List: 1 -> 2 -> 3 -> 2 -> 1
5
6Iteration 2:
7pre -> 2
8cur -> 1
9Reversed part: None <- 3 <- 2 List: 1 -> 2 -> 3 -> 2 -> 1
10
11Iteration 3:
12pre -> 1
13cur -> None
14Reversed part: None <- 3 <- 2 <- 1

After reversing, we have pre pointing to the new head of the reversed second half, which is the node with the value 1.

Step 3: Compare Two Halves

We now have two pointers, head pointing to the first node of the list and pre pointing to the head of the reversed second half. We need to compare the values of both halves:

1pre points to 1, head points to 1

We move both pointers and compare their values:

1pre -> 2, head -> 2 (values match, move forward)
2pre -> 3, head -> 3 (values match, move forward)

When pre becomes None, we've successfully compared all nodes of the reversed half with the corresponding nodes of the first half and found that all the values match, which implies that the list represents a palindrome. Hence, we return True.

When implementing these steps in a programming language like Python, the overall result of this example would be that the function confirms the linked list [1 -> 2 -> 3 -> 2 -> 1] is indeed a palindrome.

Python Solution

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, val=0, next_node=None):
4        self.val = val
5        self.next = next_node
6
7class Solution:
8    def isPalindrome(self, head: Optional[ListNode]) -> bool:
9        # Initialize two pointers, slow moves one step at a time, fast moves two steps
10        slow = head
11        fast = head.next
12      
13        # Move fast pointer to the end of the list, and slow to the middle
14        while fast and fast.next:
15            slow = slow.next
16            fast = fast.next.next
17      
18        # Reverse the second half of the list
19        prev = None
20        current = slow.next
21        while current:
22            temp = current.next
23            current.next = prev
24            prev, current = current, temp
25      
26        # Compare the first half and the reversed second half
27        while prev:
28            if prev.val != head.val:
29                return False
30            prev, head = prev.next, head.next
31      
32        # If all nodes matched, it's a palindrome
33        return True
34

Java Solution

1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12class Solution {
13    public boolean isPalindrome(ListNode head) {
14        // Use two pointers: slow moves one step at a time and fast moves two steps at a time.
15        ListNode slow = head;
16        ListNode fast = head;
17
18        // Move fast pointer to the end, and slow to the middle of the list
19        while (fast != null && fast.next != null) {
20            slow = slow.next;
21            fast = fast.next.next;
22        }
23
24        // Reverse the second half of the list
25        ListNode prev = null;
26        ListNode current = slow;
27        while (current != null) {
28            ListNode temp = current.next; // Stores the next node
29            current.next = prev; // Reverses the link
30            prev = current; // Moves prev to current node
31            current = temp; // Move to the next node in the original list
32        }
33
34        // Compare the reversed second half with the first half
35        ListNode firstHalfIterator = head;
36        ListNode secondHalfIterator = prev;
37        while (secondHalfIterator != null) {
38            // If values are different, then it's not a palindrome
39            if (secondHalfIterator.val != firstHalfIterator.val) {
40                return false;
41            }
42
43            // Move to the next nodes in both halves
44            secondHalfIterator = secondHalfIterator.next;
45            firstHalfIterator = firstHalfIterator.next;
46        }
47
48        // All values matched, so it's a palindrome
49        return true;
50    }
51}
52

C++ Solution

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    bool isPalindrome(ListNode* head) {
14        // Use two pointers to find the middle of the list
15        ListNode* slowPtr = head;
16        ListNode* fastPtr = head->next;
17      
18        // Move fastPtr by two and slowPtr by one step
19        // When fastPtr reaches the end, slowPtr will be at the middle
20        while (fastPtr && fastPtr->next) {
21            slowPtr = slowPtr->next;
22            fastPtr = fastPtr->next->next;
23        }
24
25        // Reverse the second half of the list
26        ListNode* prevNode = nullptr;
27        ListNode* currentNode = slowPtr->next;
28        while (currentNode) {
29            ListNode* nextTemp = currentNode->next;
30            currentNode->next = prevNode;
31            prevNode = currentNode;
32            currentNode = nextTemp;
33        }
34
35        // Compare the reversed second half with the first half
36        while (prevNode) {
37            // If the values are different, then it's not a palindrome
38            if (prevNode->val != head->val) {
39                return false;
40            }
41            // Move to the next nodes in both halves
42            prevNode = prevNode->next;
43            head = head->next;
44        }
45
46        // All values matched, so it is a palindrome
47        return true;
48    }
49};
50

Typescript Solution

1/**
2 * Function to determine if a given singly linked list is a palindrome.
3 * @param {ListNode | null} head - The head of the singly linked list.
4 * @returns {boolean} - True if the list is a palindrome, false otherwise.
5 */
6function isPalindrome(head: ListNode | null): boolean {
7    // Two pointers: slow moves one step at a time, fast moves two steps.
8    let slowPointer: ListNode | null = head;
9    let fastPointer: ListNode | null = head?.next;
10
11    // Traverse the list to find the middle
12    while (fastPointer !== null && fastPointer.next !== null) {
13        slowPointer = slowPointer.next;
14        fastPointer = fastPointer.next.next;
15    }
16
17    // Reverse the second half of the list
18    let current: ListNode = slowPointer.next;
19    slowPointer.next = null;
20    let previous: ListNode = null;
21    while (current !== null) {
22        let temp: ListNode = current.next;
23        current.next = previous;
24        previous = current;
25        current = temp;
26    }
27
28    // Compare the two halves of the list
29    while (previous !== null && head !== null) {
30        if (previous.val !== head.val) {
31            return false; // Values do not match, not a palindrome
32        }
33        previous = previous.next;
34        head = head.next;
35    }
36
37    // If all values matched, then the list is a palindrome
38    return true;
39}
40

Time and Space Complexity

The code above checks if a given singly-linked list is a palindrome. Here is the analysis of its time and space complexity:

Time Complexity

The algorithm uses two pointers (slow and fast) to find the middle of the linked list. The fast pointer moves two steps for every step the slow pointer takes. This loop will run in O(n/2) time, which is O(n) where n is the number of nodes in the list.

After finding the middle of the list, the code reverses the second half of the linked list. This is another loop that runs from the middle to the end of the list, which is also O(n/2) or simplifies to O(n).

Finally, the code compares the values of nodes from the start of the list and the start of the reversed second half. This comparison stops when the end of the reversed half is reached, which is at most n/2 steps, so O(n/2) or O(n).

The total time complexity is the sum of these steps, which are all linear with respect to the length of the linked list: O(n) + O(n) + O(n) which is O(3n) or simply O(n).

Space Complexity

There are no additional data structures used that grow with the input size. The pointers and temporary variables use a constant amount of space regardless of the size of the linked list. Therefore, the space complexity is O(1), which means it is constant.

So, the overall time complexity of the algorithm is O(n), and the space complexity is O(1).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫