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.

Learn more about Stack, Recursion, Linked List and Two Pointers patterns.

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.

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.

Solution Implementation

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).

Learn more about how to find time and space complexity quickly using problem constraints.