How to Determine a Palindrome Linked List

In the previous article Summary of Two-Pointer Techniques for Arrays, we discussed problems related to palindromic strings and sequences. Let's briefly review.

The core idea of finding palindromic strings is to expand from the center to both ends:

// Find the longest palindrome in s with s[left] and s[right] as the center
String palindrome(String s, int left, int right) {
    // Prevent index out of bounds
    while (left >= 0 && right < s.length()
            && s.charAt(left) == s.charAt(right)) {
        // Two pointers, expand to both sides
        left--;
        right++;
    }
    // Return the longest palindrome with s[left] and s[right] as the center
    return s.substring(left + 1, right);
}

// Find the longest palindrome in s with s[left] and s[right] as the center
string palindrome(string s, int left, int right) {
    // Prevent index out of bounds
    while (left >= 0 && right < s.length()
            && s[left] == s[right]) {
        // Two pointers, expand to both sides
        left--;
        right++;
    }
    // Return the longest palindrome with s[left] and s[right] as the center
    return s.substr(left + 1, right - left - 1);
}

# Find the longest palindrome in s with s[left] and s[right] as the center
def palindrome(s: str, left: int, right: int) -> str:
    # Prevent index out of bounds
    while left >= 0 and right < len(s) and s[left] == s[right]:
        # Two pointers, expand to both sides
        left -= 1
        right += 1
    # Return the longest palindrome with s[left] and s[right] as the center
    return s[(left + 1):right]

// Find the longest palindrome in s with s[left] and s[right] as the center
func palindrome(s string, left int, right int) string {
    // Prevent index out of bounds
    for left >= 0 && right < len(s) && s[left] == s[right] {
        // Two pointers, expand to both sides
        left--
        right++
    }
    // Return the longest palindrome with s[left] and s[right] as the center
    return s[(left + 1):right]
}

// Find the longest palindrome in s with s[left] and s[right] as the center
var palindrome = function(s, left, right) {
    // prevent index out of bounds
    while (left >= 0 && right < s.length && s.charAt(left) == s.charAt(right)) {
        // two pointers, expand to both sides
        left--;
        right++;
    }
    // return the longest palindrome with s[left] and s[right] as the center
    return s.substring(left + 1, right);
};

Since the length of a palindrome can be either odd or even, there is only one center point when the length is odd, and there are two center points when the length is even. Therefore, the function above needs to take l and r as inputs.

However, determining whether a string is a palindrome is much simpler. You don't need to consider the parity of the length. You just need to use the Two-Pointer Technique, approaching from both ends towards the middle:

boolean isPalindrome(String s) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

bool isPalindrome(string s) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

def isPalindrome(s: str) -> bool:
    # two pointers, one on the left and one on the right, moving towards each other
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

func isPalindrome(s string) bool {
    // two pointers, one on the left and one on the right, moving towards each other
    left, right := 0, len(s) - 1
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

var isPalindrome = function(s) {
    // two pointers, one on the left and one on the right, move towards each other
    let left = 0, right = s.length - 1;
    while (left < right) {
        if (s.charAt(left) !== s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
};

The above code is quite straightforward, because palindromes are symmetric, they should read the same forwards and backwards. This characteristic is key to solving palindrome problems.

Now, let's extend this simplest case to solve: how to determine if a "singly linked list" is a palindrome.

I. Determining if a Singly Linked List is a Palindrome

Take a look at LeetCode problem #234 "Palindrome Linked List":

234. Palindrome Linked List | LeetCode |

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

Constraints:

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

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

The function signature is as follows:

boolean isPalindrome(ListNode head);

The crux of this problem is that a singly linked list cannot be traversed backwards, making it impossible to use the two-pointer technique.

The simplest approach is to reverse the original list and store it in a new list, then compare the two lists to see if they are the same. For how to reverse a linked list, you can refer to the previous article Recursively Reversing a Part of a Linked List.

In Framework Thinking for Learning Data Structures, I mentioned that linked lists have a recursive structure, and tree structures are merely extensions of linked lists. Therefore, linked lists can also have pre-order and post-order traversals. By borrowing the idea of post-order traversal from binary trees, we can traverse a linked list in reverse without explicitly reversing the original list:

// Binary tree traversal framework
void traverse(TreeNode root) {
    // Pre-order traversal code
    traverse(root.left);
    // In-order traversal code
    traverse(root.right);
    // Post-order traversal code
}

// Recursively traverse a single linked list
void traverse(ListNode head) {
    // Pre-order traversal code
    traverse(head.next);
    // Post-order traversal code
}

// Binary tree traversal framework
void traverse(TreeNode* root) {
    // Pre-order traversal code
    traverse(root->left);
    // In-order traversal code
    traverse(root->right);
    // Post-order traversal code
}

// Recursively traverse a single linked list
void traverse(ListNode* head) {
    // Pre-order traversal code
    traverse(head->next);
    // Post-order traversal code
}

# Binary tree traversal framework
def traverse(root: TreeNode) -> None:
    # Pre-order traversal code
    traverse(root.left)
    # In-order traversal code
    traverse(root.right)
    # Post-order traversal code

# Recursively traverse a single linked list
def traverse(head: ListNode) -> None:
    # Pre-order traversal code
    traverse(head.next)
    # Post-order traversal code

// Binary tree traversal framework
func traverse(root *TreeNode) {
    // Pre-order traversal code
    traverse(root.left)
    // In-order traversal code
    traverse(root.right)
    // Post-order traversal code
}

// Recursively traverse a single linked list
func traverse(head *ListNode) {
    // Pre-order traversal code
    traverse(head.Next)
    // Post-order traversal code
}

// Binary tree traversal framework
var traverse = function(root) {
    // Pre-order traversal code
    traverse(root.left);
    // In-order traversal code
    traverse(root.right);
    // Post-order traversal code
};

// Recursively traverse a single linked list
var traverse = function(head) {
    // Pre-order traversal code
    traverse(head.next);
    // Post-order traversal code
};

What is the guiding significance of this framework? If you want to print the val values in a linked list in order, you can write code at the pre-order traversal position; conversely, if you want to traverse the linked list in reverse order, you can operate at the post-order traversal position:

// Print the element values in a singly linked list in reverse order
void traverse(ListNode head) {
    if (head == null) return;
    traverse(head.next);
    // Post-order traversal code
    print(head.val);
}

// Print the elements of a singly linked list in reverse order
void traverse(ListNode* head) {
    if (head == NULL) return;
    traverse(head->next);
    // Post-order traversal code
    print(head->val);
}

# Print the element values in the single linked list in reverse order
def traverse(head: ListNode):
    if head is None:
        return
    traverse(head.next)
    # Post-order traversal code
    print(head.val)

// Print the element values in the single linked list in reverse order
func traverse(head *ListNode) {
    if head == nil {
        return
    }
    traverse(head.Next)
    // Post-order traversal code
    print(head.Val)
}

// Print the elements of a singly linked list in reverse order
function traverse(head) {
  if (head === null) {
    return;
  }
  traverse(head.next);
  // Post-order traversal code
  console.log(head.val);
}

Speaking of this, we can actually make a slight modification to mimic the two-pointer technique for implementing palindrome checking functionality:

class Solution {
    // pointer moving from left to right
    ListNode left;
    // pointer moving from right to left
    ListNode right;

    // record if the linked list is a palindrome
    boolean res = true;

    boolean isPalindrome(ListNode head) {
        left = head;
        traverse(head);
        return res;
    }

    void traverse(ListNode right) {
        if (right == null) {
            return;
        }

        // use recursion to reach the end of the linked list
        traverse(right.next);

        // in post-order traversal, the right pointer points to the end of the linked list
        // so we can compare it with the left pointer to check if it's a palindrome linked list
        if (left.val != right.val) {
            res = false;
        }
        left = left.next;
    }
}

class Solution {
public:
    // pointer moving from left to right
    ListNode* left;
    // pointer moving from right to left
    ListNode* right;

    // record if the linked list is a palindrome
    bool res = true;

    bool isPalindrome(ListNode* head) {
        left = head;
        traverse(head);
        return res;
    }

    void traverse(ListNode* right) {
        if (right == nullptr) {
            return;
        }

        // use recursion to reach the end of the linked list
        traverse(right->next);

        // in post-order position, the right pointer is at the end of the linked list
        // so we can compare it with the left
        // pointer to check if the linked list is a
        if (left->val != right->val) {
            res = false;
        }
        left = left->next;
    }
};

class Solution:
    # pointer moving from left to right
    left = None
    # pointer moving from right to left
    right = None

    # record whether the linked list is a palindrome
    res = True

    def isPalindrome(self, head: ListNode) -> bool:
        self.left = head
        self.traverse(head)
        return self.res

    def traverse(self, right: ListNode):
        if right is None:
            return

        # use recursion to reach the end of the linked list
        self.traverse(right.next)

        # in the post-order position, the right pointer points to the end of the linked list
        # so it can be compared with the left
        # pointer to determine if it is a palindrome
        if self.left.val != right.val:
            self.res = False
        self.left = self.left.next

func isPalindrome(head *ListNode) bool {
    // pointer moving from left to right
    left := head
    // pointer moving from right to left
    var right *ListNode

    // record whether the linked list is a palindrome
    res := true

    var traverse func(right *ListNode)
    traverse = func(right *ListNode) {
        if right == nil {
            return
        }

        // use recursion to reach the end of the linked list
        traverse(right.Next)

        // post-order traversal position, at this time the right
        // pointer points to the tail of the right side of the
        // so it can be compared with the left pointer
        // to determine whether it is a palindrome
        if left.Val != right.Val {
            res = false
        }
        left = left.Next
    }

    right = head
    traverse(right)
    return res
}

var isPalindrome = function(head) {
    // pointer moving from left to right
    let left = head;
    // pointer moving from right to left
    let right = null;

    // record whether the linked list is a palindrome
    let res = true;

    var traverse = function(right) {
        if (right === null) {
            return;
        }

        // use recursion to reach the end of the linked list
        traverse(right.next);

        // postorder traversal position, at this point the
        // right pointer points to the right end of the
        // so we can compare with the left pointer
        // to determine if it is a palindrome linked
        if (left.val !== right.val) {
            res = false;
        }
        left = left.next;
    };

    right = head;
    traverse(right);
    return res;
};

What is the core logic behind this approach? Essentially, it involves placing the linked list nodes into a stack and then retrieving them, which reverses the order of the elements. We are simply utilizing the call stack of the recursive function. If this is hard to grasp, you can refer to the visualization panel below. By continuously clicking on the line of code traverse(right.next);, you can observe the movement process of left and right:

Of course, whether you create a reversed linked list or use post-order traversal, the time and space complexity of the algorithm remains O(N). Now, let's think about whether we can solve this problem without using extra space.

II. Optimizing Space Complexity

A better approach is as follows:

1. First, use the fast and slow pointer technique from Linked List Pointer Techniques to find the midpoint of the linked list:

ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// the slow pointer now points to the middle of the linked list

ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next->next;
}
// the slow pointer now points to the middle of the linked list

slow, fast = head, head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
# the slow pointer now points to the middle of the linked list

var slow, fast *ListNode
slow, fast = head, head
for fast != nil && fast.Next != nil {
    slow = slow.Next
    fast = fast.Next.Next
}
// slow now points to the middle of the linked list

var slow, fast;
slow = fast = head;
while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
}
// the slow pointer now points to the middle of the linked list

2. If the fast pointer is not pointing to null, it indicates the linked list has an odd length, and slow needs to move one more step forward:

if (fast != null)
    slow = slow.next;

3. Begin reversing the linked list from the slow pointer onward, and now you can start comparing for palindrome:

ListNode left = head;
ListNode right = reverse(slow);

while (right != null) {
    if (left.val != right.val)
        return false;
    left = left.next;
    right = right.next;
}
return true;

ListNode* left = head;
ListNode* right = reverse(slow);

while (right != nullptr) {
    if (left->val != right->val)
        return false;
    left = left->next;
    right = right->next;
}
return true;

left, right = head, reverse(slow)

while right:
    if left.val != right.val:
        return False
    left, right = left.next, right.next

return True

left := head
right := reverse(slow)

for right != nil {
    if left.Val != right.Val {
        return false
    }
    left = left.Next
    right = right.Next
}

return true

let left = head;
let right = reverse(slow);

while (right !== null) {
    if (left.val !== right.val)
        return false;
    left = left.next;
    right = right.next;
}

return true;

So far, combining the above 3 segments of code efficiently solves the problem. You can refer to the reverse function in Reverse a Singly Linked List:

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode slow, fast;
        slow = fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        if (fast != null)
            slow = slow.next;
        
        ListNode left = head;
        ListNode right = reverse(slow);
        while (right != null) {
            if (left.val != right.val)
                return false;
            left = left.next;
            right = right.next;
        }
        
        return true;
    }

    ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow, *fast;
        slow = fast = head;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        if (fast != nullptr)
            slow = slow->next;
        
        ListNode* left = head;
        ListNode* right = reverse(slow);
        while (right != nullptr) {
            if (left->val != right->val)
                return false;
            left = left->next;
            right = right->next;
        }
        
        return true;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr, *cur = head;
        while (cur != nullptr) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
};

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        if fast:
            slow = slow.next
        
        left = head
        right = self.reverse(slow)
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        
        return True

    def reverse(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            next = cur.next
            cur.next = pre
            pre = cur
            cur = next
        return pre

func isPalindrome(head *ListNode) bool {
	var slow, fast *ListNode
	slow, fast = head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}

	if fast != nil {
		slow = slow.Next
	}

	left, right := head, reverse(slow)
	for right != nil {
		if left.Val != right.Val {
			return false
		}
		left = left.Next
		right = right.Next
	}

	return true
}

func reverse(head *ListNode) *ListNode {
	var pre, cur *ListNode
	pre, cur = nil, head
	for cur != nil {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

var isPalindrome = function(head) {
    let slow, fast;
    slow = fast = head;
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    if (fast !== null)
        slow = slow.next;

    let left = head;
    let right = reverse(slow);
    while (right !== null) {
        if (left.val !== right.val)
            return false;
        left = left.next;
        right = right.next;
    }
    
    return true;
};

function reverse(head) {
    let pre = null, cur = head;
    while (cur !== null) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

The algorithm process is shown in the GIF below:

The overall time complexity of the algorithm is O(N), and the space complexity is O(1), which is optimal.

I know some readers might ask: Although this solution is efficient, it alters the original structure of the input linked list. Can this flaw be avoided?

Actually, this issue can be easily resolved. The key is to get the positions of the pointers p and q:

Thus, you can restore the original order of the linked list by adding a piece of code before the function returns:

p.next = reverse(q);

Due to space constraints, I won’t elaborate further here. Readers can try it themselves.

3. Final Summary

First, finding a palindrome involves expanding from the center to both ends, while checking for a palindrome involves shrinking from both ends to the center. For a singly linked list, direct reverse traversal is not possible, but you can create a new reversed linked list, utilize post-order traversal of the list, or use a stack structure to process the list in reverse.

Specifically for checking palindrome linked lists, due to the unique nature of palindromes, it's possible to only partially reverse the list, thereby reducing the space complexity to O(1).