Teaching Kids Programming: Videos on Data Structures and Algorithms
Given a singly linked list node whose values are integers, determine whether the linked list forms a palindrome.
Constraints
n ≤ 100,000 where n is the length of nodeFor example, 1 – 2 – 3 is not a palindrome linked list but 1 – 2 – 1 is
Linked List Palindrome via Conversion to List
Most Linked List problems can be solved by converting the linked list to a normal list (using O(N) space) so that we can random access the element in the list using O(1).
The following traverses the linked list and converts the data into a list, and then check if an array is a palindrome – which can be done several ways in O(N) time.
The overall time and space complexity is O(N).
1 2 3 4 5 6 7 8 9 10 11 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def solve(self, node): data = [] while node: data.append(node.val) node = node.next return data[::-1] == data |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def solve(self, node):
data = []
while node:
data.append(node.val)
node = node.next
return data[::-1] == dataChecking Palindrome Linked List via Using Stack
We can walk through the linked list and append the values one by one to stack, then if we walk from the begining and pop elements from the stack – they should equal if it is a palindrome list.
The time and space complexity is both O(N) – as we are using a list/stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def solve(self, node): data = [] head = node while head: data.append(head.val) head = head.next head = node while head: if data[-1] != head.val: return False data.pop() head = head.next return True |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def solve(self, node):
data = []
head = node
while head:
data.append(head.val)
head = head.next
head = node
while head:
if data[-1] != head.val:
return False
data.pop()
head = head.next
return TrueReverse Second Half of Linked List
We can use the fast and slow pointer to get the middle of the linked list – then if break the linked list in the middle and reverse the second half, both linked lists should equal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def solve(self, node): fast, slow = node, node while fast and fast.next: fast = fast.next.next slow = slow.next right = None while slow: p = slow.next slow.next = right right = slow slow = p left = node while left and right: if left.val != right.val: return False left = left.next right = right.next return True |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def solve(self, node):
fast, slow = node, node
while fast and fast.next:
fast = fast.next.next
slow = slow.next
right = None
while slow:
p = slow.next
slow.next = right
right = slow
slow = p
left = node
while left and right:
if left.val != right.val:
return False
left = left.next
right = right.next
return TrueTime complexity is O(N) and space is O(1) but we are modifying the original linked list.
Recursive Algorithm to Check Palindrome Linked Lists
Recursion is based on stack – thus we can move the head pointer after recursion, and then use this to compare the corresponding node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | # class LLNode: # def __init__(self, val, next=None): # self.val = val # self.next = next class Solution: def solve(self, node): root = node def dfs(node): if node is None: return True nonlocal root ans = dfs(node.next) if root.val != node.val: return False root = root.next return ans return dfs(node) |
# class LLNode:
# def __init__(self, val, next=None):
# self.val = val
# self.next = next
class Solution:
def solve(self, node):
root = node
def dfs(node):
if node is None:
return True
nonlocal root
ans = dfs(node.next)
if root.val != node.val:
return False
root = root.next
return ans
return dfs(node)Time and space complexity is O(N).
See also: How to Reverse Linked List within Interval? (C/C++)
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Dynamic Programming Algorithms to Compute the Maximum Non-Adjacent Tree Sum
Next Post: Java Program to Print All Local IP Addresses
