Home/

...

/

Problem Challenge 1

Problem Challenge 1

Resources for checking if a LinkedList is a palindrome.

Problem statement

Given the head of a singly linked list, check if it is a palindrome. Your algorithm should use constant space and the input linked list should be in its original state once the algorithm has ended. The algorithm should have O(n)O(n) time complexity where nn is the number of nodes in the linked list.

Dry-run templates

This is the implementation of the solution provided for the problem posed in the lesson:

Press + to interact
Python 3.5
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def is_palindromic_linked_list(head):
  if head is None or head.next is None:
    return True
  # find middle of the LinkedList
  slow, fast = head, head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  head_second_half = reverse(slow)  # reverse the second half
  # store the head of reversed part to revert back later
  copy_head_second_half = head_second_half
  # compare the first and the second half
  while (head is not None and head_second_half is not None):
    if head.value != head_second_half.value:
      break  # not a palindrome
    head = head.next
    head_second_half = head_second_half.next
  reverse(copy_head_second_half)  # revert the reverse of the second half
  if head is None or head_second_half is None:  # if both halves match
    return True
  return False
def reverse(head):
  prev = None
  while (head is not None):
    next = head.next
    head.next = prev
    prev = head
    head = next
  return prev
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(4)
  head.next.next.next.next = Node(2)
  print("Is palindrome: " + str(is_palindromic_linked_list(head)))
  head.next.next.next.next.next = Node(2)
  print("Is palindrome: " + str(is_palindromic_linked_list(head)))
main()

Students may be encouraged to run through the provided solution with the following sample inputs.

Sample input #1

2 -> 4 -> 6 -> 6 -> 4 -> 2 -> null

The reverse() function simply reverses the provided linked list. The dry-run table below does not show how the reversing process takes place.

First while loop Iteration

Second while loop iteration

Line number

head

slow

fast

head_second_half

-

-

12

2

2

2

-

1

-

13-15

2

4

6

-

2

-

13-15

2

6

4

-

3

-

13-15

2

6

None

-

-

-

17

2

6

None

2

-

1

22-27

4

6

None

4

-

2

22-27

6

6

None

6

-

3

22-27

6

6

None

None

Sample input #2

2 -> 4 -> 6 -> 4 -> 2 -> 2 -> null

First while loop Iteration

Second while loop iteration

Line number

head

slow

fast

head_second_half

-

-

12

2

2

2

-

1

-

13-15

2

4

6

-

2

-

13-15

2

6

2

-

3

-

13-15

2

4

None

-

-

-

17

2

4

None

2

-

1

22-27

4

4

None

2

Sample input #3

2 -> 4 -> 6 -> 7 -> 4 -> 2 -> null

The students are encouraged to complete the following dry run table themselves:

First while loop Iteration

Second while loop iteration

Line number

head

slow

fast

head_second_half

-

-

12

2

2

2

-

1

-

13-15

2

4

6

-

2

-

13-15

2

6

4

-

...

...

...

...

...

...

...

Step-by-step solution construction

Our algorithm does the following:

  • We use the fast & slow pointers method to find the middle node of the linked list.
  • Once we have the middle of the linked list, we reverse the second half.
  • Then, we compare the first half with the reversed second half to see if the linked list represents a palindrome.
  • Finally, we reverse the second half of the linked list again to revert and bring the linked list back to its original form.

Let’s first see how our fast and slow pointers are updated to find the middle of the linked list. In this case, fast moves forward by a factor of 2, while slow moves by a factor of 1. This way, when fast reaches the end of the linked list, our slow pointer will be on the middle node.

In the case of an even number of nodes in the linked list, fast will point at the last node when slow reaches the middle.

However, in the case of an odd number of nodes, fast will point to None when slow reaches the middle.

Press + to interact
Python 3.5
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def is_palindromic_linked_list(head):
  if head is None or head.next is None:
    return True
  # find middle of the LinkedList
  slow, fast = head, head
  print("Slow: ", slow.value)
  print("Fast: ", fast.value, "\n")
  i = 1
  while (fast is not None and fast.next is not None):
    print("Loop index: ", i)
    i+=1
    slow = slow.next
    fast = fast.next.next
    print("Slow: ", slow.value)
    if fast == None:
      print("Fast: None\n")
    else:
      print("Fast: ", fast.value, "\n")
  print("Middle node: ", slow.value, "\n")
def print_list_with_forwardarrow(self):
  temp = self
  while temp is not None:
    print(temp.value, end=" ") #print node value
    
    temp = temp.next
    if temp is None:
      print("--> null") # if this is the last node, print null at the end
    else:
      print("-->", end=" ") 
  print()
  
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(6)
  head.next.next.next.next = Node(4)
  head.next.next.next.next.next = Node(2)
  head2 = Node(2)
  head2.next = Node(4)
  head2.next.next = Node(6)
  head2.next.next.next = Node(4)
  head2.next.next.next.next = Node(2)
  head2.next.next.next.next.next = Node(2)
  head3 = Node(2)
  head3.next = Node(4)
  head3.next.next = Node(6)
  head3.next.next.next = Node(7)
  head3.next.next.next.next = Node(4)
  head3.next.next.next.next.next = Node(2)
  input = [head, head2, head3]
  for i in input:
    print("Input linked list: ")
    print_list_with_forwardarrow(i)
    print("Is palindrome: " + str(is_palindromic_linked_list(i)), "\n")
    print("-"*100 + "\n")	
main()

Note: print_list_with_forwardarrow() function is only for printing the linked list and is independent of the algorithm.

Once we’ve found the middle, we call the reverse() function on the second half of the linked list to reverse the nodes. This makes it easier to compare them with the first half. Here’s what we’ll do in our reverse() function:

  • Make a dummy pointer prev that points to None.
  • Temporarily store head's next node in a new variable.
  • Reverse the head node.
  • Point the prev node to the head before moving to the next node.
  • Move the head pointer one step ahead.

Let’s see this in action:

Press + to interact
Python 3.5
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def is_palindromic_linked_list(head):
  if head is None or head.next is None:
    return True
  # find middle of the LinkedList
  slow, fast = head, head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  print("Middle node: ", slow.value, "\n")
  print("Second half: ")
  print_list_with_forwardarrow(slow)
  print("Reversing the second half \n")
  head_second_half = reverse(slow)  # reverse the second half
  print("\n\nReversed linked list: ")
  print_list_with_backarrow(head_second_half)
  print(" ")
  # store the head of reversed part to revert back later
  copy_head_second_half = head_second_half
  # compare the first and the second half
  while (head is not None and head_second_half is not None):
    if head.value != head_second_half.value:
      break  # not a palindrome
    head = head.next
    head_second_half = head_second_half.next
  print("\nReverting the reversed second half")
  reverse(copy_head_second_half)  # revert the reverse of the second half
  print("\n")
  return False
def print_list_with_forwardarrow(self):
  temp = self
  while temp is not None:
    print(temp.value, end=" ") #print node value
    
    temp = temp.next
    if temp is None:
      print("--> null") # if this is the last node, print null at the end
    else:
      print("-->", end=" ") 
  print()
def print_list_with_backarrow(self):
  temp = self
  nodes = []
  # add values of nodes from the linkedlist to the array "nodes"
  while temp is not None:
    nodes.append(temp.value)
    temp = temp.next
  # print the array "nodes" in the reverse order seperated by "<--"
  for (index,value) in enumerate(reversed(nodes)) :
    if index == 0:
        print("null <--",end=" ")
    else:
        print ("<--",end=" ")
    print(value, end=" ")
def reverse(head):
  prev = None
  index = 0
  while (head is not None):
    print("Iteration " + str(index) + ": ",end=" ")
    index +=1
    next = head.next  # temporarily store the next node
    head.next = prev  # reverse the current node
    prev = head # before we move to the next node, point previous to the current node
    print_list_with_backarrow(head)
    head = next # move on the next node
    if head is not None:
      print("   ||   ", end=" ")
      print_list_with_forwardarrow(head)
  return prev
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(6)
  head.next.next.next.next = Node(4)
  head.next.next.next.next.next = Node(2)
  head2 = Node(2)
  head2.next = Node(4)
  head2.next.next = Node(6)
  head2.next.next.next = Node(4)
  head2.next.next.next.next = Node(2)
  head2.next.next.next.next.next = Node(2)
  head3 = Node(2)
  head3.next = Node(4)
  head3.next.next = Node(6)
  head3.next.next.next = Node(7)
  head3.next.next.next.next = Node(4)
  head3.next.next.next.next.next = Node(2)
  input = [head, head2, head3]
  for i in input:
    print("Input linked list: ")
    print_list_with_forwardarrow(i)
    print("Is palindrome: " + str(is_palindromic_linked_list(i)))
    print("-"*100 + "\n")	
main()

The code first reverses the second half of the linked list and then re-reverts it to its original form. The output shows a step-by-step reversal.

Note: The print_list_with_forwardarrow() and print_list_with_backarrow() functions are only for printing the lists. They do not affect the code execution.

Once we’ve reversed our second half, the next step is to compare the two halves. At this stage, our head pointer is pointing to the first node and the head_second_half pointer is pointing to the middle node. We’ll increment both of them together and compare the node values. If they are the same until one or both of the pointers become None, we have a palindrome.

Press + to interact
Python 3.5
class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next = next
def is_palindromic_linked_list(head):
  if head is None or head.next is None:
    return True
  # find middle of the LinkedList
  slow, fast = head, head
  while (fast is not None and fast.next is not None):
    slow = slow.next
    fast = fast.next.next
  print("Middle node: ", slow.value, "\n")
  head_second_half = reverse(slow)  # reverse the second half
  print("First half: ")
  print_list(head, slow)
  print("Reversed second half: ")
  print_list_with_backarrow(head_second_half)
  print("\n")
  # store the head of reversed part to revert back later
  copy_head_second_half = head_second_half
  # compare the first and the second half
  while (head is not None and head_second_half is not None):
    print("Head: ", head.value)
    print("Head second half: ", head_second_half.value)
    if head.value != head_second_half.value:
      break  # not a palindrome
    print("Both values are the same, incrementing the pointers.\n")
    head = head.next
    head_second_half = head_second_half.next
  reverse(copy_head_second_half)  # revert the reverse of the second half
  
  if head is None or head_second_half is None:  # if both halves match
    print("Head: None\nHead second half: None\n")
    return True
  print("Both pointers are not pointing to the same value, hence, the linked list is not a palindrome.\n")
  return False
def print_list_with_forwardarrow(self):
  temp = self
  while temp is not None:
    print(temp.value, end=" ") #print node value
    
    temp = temp.next
    if temp is None:
      print("--> null") # if this is the last node, print null at the end
    else:
      print("-->", end=" ") 
  print()
def print_list(self, slow):
  temp = self
  while temp is not slow.next:
    print(temp.value, end=" ") #print node value
    
    temp = temp.next
    if temp is slow.next:
      print("") # if this is the last node, print null at the end
    else:
      print("-->", end=" ") 
  print()
def print_list_with_backarrow(self):
  temp = self
  nodes = []
  # add values of nodes from the linkedlist to the array "nodes"
  while temp is not None:
    nodes.append(temp.value)
    temp = temp.next
  # print the array "nodes" in the reverse order seperated by "<--"
  for (index,value) in enumerate(reversed(nodes)) :
    if index == 0:
        print("null <--",end=" ")
    else:
        print ("<--",end=" ")
    print(value, end=" ")
def reverse(head):
  prev = None
  while (head is not None):
    next = head.next  # temporarily store the next node
    head.next = prev  # reverse the current node
    prev = head # before we move to the next node, point previous to the current node
    head = next # move on the next node
  return prev
def main():
  head = Node(2)
  head.next = Node(4)
  head.next.next = Node(6)
  head.next.next.next = Node(6)
  head.next.next.next.next = Node(4)
  head.next.next.next.next.next = Node(2)
  head2 = Node(2)
  head2.next = Node(4)
  head2.next.next = Node(6)
  head2.next.next.next = Node(4)
  head2.next.next.next.next = Node(2)
  head2.next.next.next.next.next = Node(2)
  head3 = Node(2)
  head3.next = Node(4)
  head3.next.next = Node(6)
  head3.next.next.next = Node(7)
  head3.next.next.next.next = Node(4)
  head3.next.next.next.next.next = Node(2)
  input = [head, head2, head3]
  for i in input:
    print("Input linked list: ")
    print_list_with_forwardarrow(i)
    print("Is palindrome: " + str(is_palindromic_linked_list(i)))
    print("-"*100 + "\n")	
main()

Note: The print_list_with_forwardarrow(), print_list_with_backarrow() and print_list() functions are only for printing the lists. They do not affect the code execution.

Once the comparison is done, the reversed second half is reverted again to match the original form of the linked list. We’ve seen this step above while discussing the reverse() function.