Python Algorithm Q13

Q13 Palindrome Linked List

---

Q

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

Sample Input

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

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

Constraints

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

1. My Solution <- Given Solution #1

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

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True #to prevent when input is 0 node. "But" in this Q, it's meaningless

        ansl :list = []
        node = head

        while node is not None:
            ansl.append(node.val)
            node = node.next

        while len(ansl)>1: #if len = 1, stop. Actually single letter left so true.
            if ansl.pop(0) != ansl.pop():
                return False
        
        return True

#To test, you have to make to linked-list manually.
#In the problem, it makes the linked list automatically
inp = [1,2,2,1] #inp = input as head

head = ListNode(inp[0])
node1 = ListNode(inp[1])
node2 = ListNode(inp[2])
node3 = ListNode(inp[3])
head.next = node1
node1.next = node2
node2.next = node3 #node3's next is none.
'''
to make it shorten, do like this
node3 = ListNode(inp[3])
node2 = ListNode(inp[2], node3)
node1 = ListNode(inp[1], node2)
head = ListNode(inp[0], node1)
'''

#for test
a = Solution()
a.isPalindrome(head)

The concept itself is definitely simple. Move values in the linked list to the single list. Then do as we did before.

Before we start, to be familiar with linked list, take a time to understand. Let’s see the code below the funtion, starting with “#To test~”. I made a linked list, based on the given head. The object ListNode is an address itself, and get two value as arguments: value and the address of the next node. Therefore node = node.next is assigning address of the next one to the current one.

2. Given Solution #2

def isPalindrome(self, head: ListNode) -> bool:
        if not head:
            return True

        ansl :Deque = collections.deque()
        node = head

        while node is not None:
            ansl.append(node.val)
            node = node.next

        while len(ansl)>1:
            if ansl.popleft() != ansl.pop():
                return False
        
        return True

The only differnce from the first answer is the usage of the type “deque”. As I mentioned before, “pop” method of the type list is time-consuming. pop() takes the last value from the list, so it’s not problem at all. But when it comes to pop(0), problem occurs. All value is shifted one by one, so it takes O(n) time.

3. Given Solution #3

def isPalindrome(self, head: ListNode) -> bool:
    rev = None #define address of reverse string as null
    slow = fast = head #set start point

    while fast and fast.next: #when both are true
        fast = fast.next.next
        rev, rev.next, slow = slow, rev, slow.next
        #refer the explanation below. **Really*# Difficult.

    if fast:
        slow = slow.next #when odd length, move one more

    while rev and (rev.val==slow.val):
        slow, rev = slow.next, rev.next
    return not rev
    '''
    Do it until rev reaches the end or not palindrome.
    when reaches the end, it means palindrome.
    At the end, rev itself is none. So not rev == True 
    when stops in the middle, it means not palindrome.
    This time rev has value. So not rev == False
    '''

This is the solution using the “Runner” Method. Fast Runner jumps two-steps, and Slow Runner jumps one steps. Therefore when the fast runner reaches the end, the slow runner reaches the half point(or one step less than the half when length is odd number).

By using this method, you can search exactly half point of the list. You can reverse or compare values by utilizing the half point.

From now on, let’s focus the line in the question.

rev, rev.next, slow = slow, rev, slow.next

You can describe the loop above like this.

1. rev : 1-> None, slow : 2-> 3-> 4-> 5-> None
2. rev : 2-> 1-> None, slow : 3-> 4-> 5-> None
3. rev : 3-> 2-> 1-> None, slow : 4-> 5-> None
4. rev : 4-> 3-> 2-> 1-> None, slow : 5-> None
5. rev : 5-> 4-> 3-> 2-> 1-> None, slow : None

Refer to the posting named “linked-list” in python tips. There, you can find insertion of node at the head.

if index == 0:
    new_node.next = self.head
    self.head = new_node
    return

Just assign address of the head node to the new node. That’s all. Let’s do that in this problem.

new_node = node #the node to insert
new_node.next = rev #assign address of previous head

#in the solution
rev, rev.next = node, rev
#!!YOU NEED TO UNDERSTAND THE FEATURE OF MULTI - ASSIGNMENT!!
#This is same as
A = node
B = rev
rev = A #from now on, call rev = A = new_node
rev.next = B

Look the code above.

• A is the node to insert in front of the head.
• B is the current head of linked-list “rev”.
• by “rev = A”, you assign the node to insert to the head.
• by “rev.next = B”, after you assign the node to the head

** 보충 설명

1. 다중 할당에 의해 A에는 삽입하려 하는 node가, B에는 기존의 head node인 rev가 저장된다.
2. 그 후에 head node인 rev에 새로 넣을 node인 A를 할당한다. 이때 rev는 이미 B에 저장되어 있기 때문에 그냥 변수를 재활용한 것이지 head node가 지워지거나 하지는 않는다. 따라서 rev를 아래부터는 new_node라고 칭하겠다.
3. new_node가 이전 head node인 rev를 가르킬 수 있도록 B를 할당한다.

By repeating this process, you can progressively extend the linked-list, “rev”.

Overall Review

The solutions using list and deque is easy enough to understand. Actually, reading some postings about linked-list, I can solve with solution #1 by myself. However solution #3 is really crazy. It is because there’s so many traps, such as multi-assignment. I have so much difficulty understanding the single line of code, rev, rev.next, slow = slow, rev, slow.next.

Although this question gives me so much experience, from linked-list to multi-assignment and so on. Keep challenging to the crazy problems certainly makes me stronger…