Linked List Is Palindrome

 

Linked List Palindrome: A linked list palindrome is a linked list that reads the same forward and backward. For example, the linked list 1 -> 2 -> 3 -> 2 -> 1 is a palindrome because it reads the same from left to right and right to left.

To check if a linked list is a palindrome, we can use the following approach:

  1. Traverse the linked list and store the values of each node in a list.
  2. Check if the list of values is equal to its reverse. If they are equal, the linked list is a palindrome.

Here's an example of a complete Python code with detailed comments:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def is_palindrome(head):
    """
    Returns True if the linked list is a palindrome,
    False otherwise.
    """
    # Step 1: Traverse the linked list and store node values in a list
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next

    # Step 2: Check if the list of values is equal to its reverse
    return values == values[::-1]


# Example usage
# Create a linked list
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(2)
node5 = ListNode(1)
head.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# Check if the linked list is a palindrome
if is_palindrome(head):
    print("Linked List is a Palindrome")
else:
    print("Linked List is Not a Palindrome")

Explanation:

  1. We define the ListNode class to represent a node in the linked list. Each node has a value and a next pointer that points to the next node in the list.
  2. The is_palindrome function takes the head of the linked list as input and returns True if the linked list is a palindrome or False otherwise.
  3. In the is_palindrome function, we traverse the linked list and store the values of each node in the values list.
  4. We then check if the values list is equal to its reverse. If they are equal, it means the linked list is a palindrome.
  5. Finally, we return True if the linked list is a palindrome and False otherwise.

Time and Space Complexity Analysis:

  • The time complexity of the is_palindrome function is O(n), where n is the number of nodes in the linked list. We traverse the linked list once to store the node values in the values list and compare it with its reverse, which takes O(n) time.
  • The space complexity is O(n) because we use the values list to store the node values. The space required scales linearly with the number of nodes in the linked list.

Let's solve a question from LeetCode using the concept of linked list palindrome. One such problem is "Palindrome Linked List" (LeetCode problem #234).

Problem Statement: Given the head of a singly linked list, return true if it is a palindrome.

Example: Input: 1 -> 2 -> 2 -> 1 Output: True

To solve this problem, we can use the same approach mentioned earlier: traverse the linked list, store the node values, and check if the values form a palindrome.

Here's the complete code to solve the problem:


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def is_palindrome(head):
    # Step 1: Traverse the linked list and store node values in a list
    values = []
    curr = head
    while curr:
        values.append(curr.val)
        curr = curr.next

    # Step 2: Check if the list of values is equal to its reverse
    return values == values[::-1]


# Example usage
# Create a linked list
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(2)
node4 = ListNode(1)
head.next = node2
node2.next = node3
node3.next = node4

# Check if the linked list is a palindrome
if is_palindrome(head):
    print("Linked List is a Palindrome")
else:
    print("Linked List is Not a Palindrome")

In this code, we create a linked list with nodes having values [1, 2, 2, 1]. We then call the is_palindrome function to check if the linked list is a palindrome. In this case, the output will be "Linked List is a Palindrome" since the linked list reads the same forward and backward.

Time and Space Complexity Analysis: The time complexity of this solution is O(n), where n is the number of nodes in the linked list. We need to traverse the entire linked list to store the node values and compare them with their reverse.

The space complexity is also O(n) because we need to store the node values in the values list, which scales linearly with the number of nodes in the linked list.

 

 

 

Next Post Previous Post