Palindrome Linked List

Q: What is the time complexity of the palindrome linked list check?

Every approach is O(L) for a list of L nodes, because each value has to be compared. Copying the values into an array or onto a stack uses O(L) extra memory; reversing the second half in place uses O(1) .

Q: How does the fast and slow pointer find the middle of a linked list?

Both start at the head, and the fast pointer takes two steps for every step of the slow one. When the fast pointer reaches the end it has covered the whole list, and the slow pointer half of it.

Q: Does reversing half of the list destroy the input?

Yes, it changes the links of the second half, and in most languages that array is the caller's own. If the list is still needed, finish the comparison without returning early, then reverse that half again. The middle node still links to the half's first node, so the list is whole again in O(1) extra memory.

EasyLinked list Fast and slow pointers Two pointers

+10

You get a singly linked list stored in two arrays of the same length. Node i holds the value values[i] and links to node next[i], -1 ends the list, and the head is node 0. The nodes are not stored in list order, so follow the links.

Return true if the values read the same from the head to the end as from the end back to the head, and false otherwise.

Function

isPalindrome(next: integer-array, values: integer-array) → boolean

nextinteger-array: the index of the node each node links to, or -1 for the last node
valuesinteger-array: the value held by each node
Returnsboolean: true if the list reads the same in both directions

Constraints

1 ≤ L ≤ 5000, where L is the length of next and of values.
-100 ≤ values[i] ≤ 100
Each next[i] is -1 or a node index from 0 to L-1.
Starting at node 0, the list visits every node exactly once and then reaches -1. There is no cycle.

Examples

Input: next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
Output: true
Explanation: The links visit nodes 0, 4, 1, 3, 2, so the list reads 3, 1, 4, 1, 3. The two 3s match, the two 1s match, and the 4 in the middle has no partner to check.

Input: next = [2, -1, 3, 1]values = [4, 4, 9, 9]
Output: true
Explanation: The list visits nodes 0, 2, 3, 1 and reads 4, 9, 9, 4, the same in both directions.

Input: next = [2, -1, 1]values = [1, 2, 1]
Output: false
Explanation: The array values is [1, 2, 1], but the list visits nodes 0, 2, 1 and reads 1, 1, 2. Backwards that is 2, 1, 1, so the answer is false.

Follow-up

Can you do it in O(L) time with O(1) extra memory?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A palindrome check pairs each value with its mirror from the other end. A singly linked list only walks forward, so the hard part is reading the back half in reverse. An array copy does that with O(L) memory, where L is the number of nodes; reversing the second half's links does it with O(1).

Copy the values into an array

Intuition

A pointer here is a node index, and moving forward is node = next[node]. Walk the list once and copy each value into an array, which you can read from both ends. Compare the first and last values, move both indices toward the middle, and return false on any mismatch. With an odd length the middle value is its own partner.

Every value has to be read, so O(L) time is the best possible. The cost is L extra integers.

Algorithm

Walk from node 0 to -1 and append each values[node] to an array.
Set i = 0 and j to the last index.
While i < j, return false if the two values differ, otherwise move i up and j down.
Return true.

def isPalindrome(next, values):
    # Write the values out in list order.
    seq = []
    node = 0
    while node != -1:
        seq.append(values[node])
        node = next[node]
    # Compare from both ends toward the middle.
    i = 0
    j = len(seq) - 1
    while i < j:
        if seq[i] != seq[j]:
            return False
        i += 1
        j -= 1
    return True

Reverse the second half in place

Intuition

Reverse the links of the back half instead of copying it: a walk from the old last node then leads toward the middle. To find the middle, move fast two links for each link slow moves, while fast has two links ahead. slow stops on the last node of the first half, the middle node when L is odd. In the first example slow goes 0 → 4 → 1 while fast goes 0 → 1 → 2, so slow stops on the 4.

Reverse the nodes after slow, then walk left from the head and right from the reversed half together: 3 with 3, then 1 with 1. The reversed half is never longer than the first half, so stopping when right ends compares exactly the pairs that matter. Each phase walks at most L nodes and stores a few integers. In R, changing next_ copies the vector once, so R uses O(L) memory.

Algorithm

Set slow = fast = 0. While next[fast] and next[next[fast]] are both not -1, move slow one link and fast two.
Reverse the list that starts at next[slow]: for each node, save its link, point it at prev, then move prev and the node forward.
Set left = 0 and right = prev, the head of the reversed half.
While right != -1, return false on a mismatch, otherwise move both pointers one link.
Return true.

def isPalindrome(next, values):
    # Find the middle: fast moves two links for every one link slow moves.
    slow = 0
    fast = 0
    while next[fast] != -1 and next[next[fast]] != -1:
        slow = next[slow]
        fast = next[next[fast]]
    # slow is the last node of the first half (the middle node when the length is odd).
    # Reverse the links of the second half.
    prev = -1
    node = next[slow]
    while node != -1:
        after = next[node]
        next[node] = prev
        prev = node
        node = after
    # prev is the old last node, now the head of the reversed half.
    left = 0
    right = prev
    while right != -1:
        if values[left] != values[right]:
            return False
        left = next[left]
        right = next[right]
    return True

Pitfalls and edge cases

Checking the arrays instead of the list. In the third example values is [1, 2, 1], but the list reads 1, 1, 2.
Testing only next[fast] != -1. fast can then jump to -1 and read next[-1], which is out of range in most languages and silently the last entry in Python and Ruby.
Comparing until left ends instead of right. The middle node still links into the old second half, so the walk from the head is the longer one.
Overwriting next[node] during the reversal before saving it, which loses the rest of the list.
In Lua and R, where arrays start at 1, reading next[node] for a 0-based node id. Read next[node + 1].

Frequently asked questions3

What is the time complexity of the palindrome linked list check?

Every approach is O(L) for a list of L nodes, because each value has to be compared. Copying the values into an array or onto a stack uses O(L) extra memory; reversing the second half in place uses O(1).

How does the fast and slow pointer find the middle of a linked list?

Both start at the head, and the fast pointer takes two steps for every step of the slow one. When the fast pointer reaches the end it has covered the whole list, and the slow pointer half of it.

Does reversing half of the list destroy the input?

Yes, it changes the links of the second half, and in most languages that array is the caller's own. If the list is still needed, finish the comparison without returning early, then reverse that half again. The middle node still links to the half's first node, so the list is whole again in O(1) extra memory.

def isPalindrome(next, values):
    # Write code here

Test #1

Test #2

Test #3

Arguments

next = [4, 3, -1, 2, 1]
values = [3, 4, 3, 1, 1]

Expected Output

true