subject

Give you the head node of a single linked list. Please judge whether the linked list is a palindrome linked list. If yes, return True; Otherwise, False is returned.

For example:

The original linked list is converted to a list: [1, 2, 2, 1], and the returned result is True

The original linked list is converted to a list: [1, 2], and the returned result is False

explain:

• When returning the result, the direction of each node in the linked list needs to be consistent with the beginning.

The definition of the known linked list node and the code for the conversion between the linked list and the list are as follows:

class ListNode:  # Single linked list
    def __init__(self, val=0, next=None):
        self.val = val  # Elements stored on linked list nodes
        self.next = next  # Point to the next linked list node


def list_to_list_node(numbers):  # Convert the list into a one-way linked list and return the head node of the linked list
    dummy_head = ListNode(0)
    pre = dummy_head
    for number in numbers:
        pre.next = ListNode(number)
        pre = pre.next
    pre = dummy_head.next
    return pre


def list_node_to_list(node):  # Convert one-way linked list to list
    result = []
    while node:
        result.append(node.val)
        node = node.next
    return result

Implementation idea 1

• Store all the data in the original linked list into a list, and then judge whether to reply
• To judge whether the list is palindrome, you can define two pointers: left and right. One moves back from the beginning and the other moves forward from the end. Each time you judge whether the elements pointed to are the same. If they are different, it means that they are not palindromes and return False directly

Code implementation 1

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        cur, length = head, 0
        result = []
        while cur is not None:  # Traverse the linked list and store the elements on all nodes in the list result
            length += 1
            result.append(cur.val)
            cur = cur.next
        left, right = 0, length - 1  # Define 2 pointers, one from the beginning and the other from the end
        while left < right:
            if result[left] != result[right]:  # If the elements corresponding to left and right are found to be inconsistent, it indicates that they are not palindromes
                return False
            left += 1
            right -= 1
        return True

• Time complexity: O(n)
• Space complexity: O(n)

Of course, after storing the linked list elements in the list result above, we can also directly compare the list with its inverted list. The code is as follows:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        cur = head
        result = []
        while cur is not None:  # Traverse the linked list and store the elements on all nodes in the list result
            result.append(cur.val)
            cur = cur.next
        return result == result[::-1]

Implementation idea 2

• It is implemented by using double pointers
• Find the intermediate node from the linked list and divide the linked list into two parts: the first half and the second half. The first half is from the head node to the intermediate node of the original linked list, and the second half is from the next node to the last node of the intermediate node of the original linked list
• Reverse the second half of the original linked list to get the reversed head node reverse_head
• Define a variable to mark the final judgment result. The default value is True
• Traverse two linked lists. The first half of the linked list moves from head, and the second half of the linked list reverses from reverse_head starts to move, and compares whether the node elements are consistent in turn. If not, mark the result as False, and break jumps out of the loop
• After the comparison, because the original linked list is divided into two parts, you need to restore the direction of the original linked list first, and then return the final judgment result

Code implementation 2

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if head is None:  # If it is an empty linked list, return True directly
            return True
        middle_node = self.get_middle_node(head)  # Find intermediate node
        reverse_head = self.reverse_list_node(middle_node.next)  # Invert from the next node of the intermediate node of the original linked list to the last node, and return the inverted head node
        flag, pre, post = True, head, reverse_head
        while post is not None:
            # The first half of the linked list starts from head, and the second half of the inverted linked list starts from reverse_ Start with head and compare whether the node elements are consistent
            if pre.val != post.val:
                flag = False
                break
            pre = pre.next
            post = post.next
        middle_node.next = self.reverse_list_node(reverse_head)  # Restore the original linked list
        return flag

    def get_middle_node(self, head: ListNode) -> ListNode:  # Find the intermediate node of the linked list
        slow, fast = head, head  # Define slow and fast pointers
        while fast.next is not None and fast.next.next is not None:
            slow = slow.next  # The slow pointer moves 1 bit at a time
            fast = fast.next.next  # The fast pointer moves 2 bits at a time
        return slow

    def reverse_list_node(self, head: ListNode) -> ListNode:  # Invert the linked list and return the inverted head node
        pre, cur = None, head
        while cur is not None:
            next_node = cur.next
            cur.next = pre
            pre = cur
            cur = next_node
        return pre

• Time complexity: O(n)
• Space complexity: O(1)

More Python programming questions are waiting for you to challenge: Python programming problem summary (continuously updated...)