Linkedlist Flashcards
Linked list functions:
object, print linkedlist, push, append
# A Linked List Node
class Node:
next = None
# Constructor
def \_\_init\_\_(self, data):
self.data = data
# Function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to insert a node at the beginning of the linked list def push(head, data):
# allocate a new node in a heap and set its data
newNode = Node(data)
# set the next field of the node to point to the current
# first node of the list.
newNode.next = head
# return the head to point to the node, so it is
# now the first node in the list.
return newNode
# Function to add a node at the tail end of the list instead # of its head def appendNode(head, key):
current = head
# special case for the empty list
if current is None:
head = push(head, key)
else:
# locate the last node
while current.next:
current = current.next
# Build the node after the last node
current.next = push(current.next, key)
return head
if __name__ == ‘__main__’:
# input keys
keys = [1, 2, 3, 4]
# points to the head node of the linked list
head = None
for key in keys:
head = appendNode(head, key)
# print linked list
printList(head)
Function to implement a linked list from a given set of keys # using a dummy node
# A Linked List Node
class Node:
# Constructor
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Takes a list and a data value, creates a new link with the given data # and pushes it onto the list's front. def push(head, data):
# allocate a new node in a heap and set its data
newNode = Node(data)
# set the next field of the node to point to the current
# first node of the list.
newNode.next = head
# change the head to point to the new node, so it is
# now the first node in the list.
return newNode
# Function to implement a linked list from a given set of keys # using a dummy node def constructList(keys):
dummy = Node() # dummy node is temporarily the first node
tail = dummy # start the tail at the dummy
# Build the list on `dummy.next` (aka `tail.next`)
for key in keys:
tail.next = push(tail.next, key)
tail = tail.next
# The real result list is now in `dummy.next`
# dummy.next == key[0], key[1], key[2], key[3]
return dummy.next
if __name__ == ‘__main__’:
# input keys
keys = [1, 2, 3, 4]
# points to the head node of the linked list
head = constructList(keys)
# print linked list
printList(head)
Clone a Linked List
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function takes a linked list and returns a complete copy of that # list using a dummy node using the `push()` function def copyList(head):
current = head # used to iterate over the original list newList = None # head of the list tail = None # point to the last node in a new list while current:
# special case for the first node
if newList is None:
newList = Node(current.data, newList)
tail = newList
else:
tail.next = Node(current.data, tail.next) # add each node at the tail
tail = tail.next # advance the tail to the new last node
current = current.next
return newList
if __name__ == ‘__main__’:
# construct a linked list
head = None
for i in reversed(range(4)):
head = Node(i + 1, head)
# copy linked list
dup = copyList(head)
# print duplicate linked list
printList(dup)
Insert a node to its correct sorted position in a sorted linked list
Given a sorted list in increasing order and a single node, insert the node into the list’s correct sorted position. The function should take an existing node and rearranges pointers to insert it into the list.
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list, and doesn’t require any extra space.
______________________________________________
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to insert a given node at its correct sorted position into # a given list sorted in increasing order def sortedInsert(head, newNode):
# special case for the head end
if head is None or head.data >= newNode.data:
newNode.next = head
head = newNode
return head
# Locate the node before the poof insertion
current = head
while current.next and current.next.data < newNode.data:
current = current.next
newNode.next = current.next current.next = newNode return head
if __name__ == ‘__main__’:
# input keys
keys = [2, 4, 6, 8]
# points to the head node of the linked list
head = None
# construct a linked list
for i in reversed(range(len(keys))):
head = Node(keys[i], head)
head = sortedInsert(head, Node(5)) head = sortedInsert(head, Node(9)) head = sortedInsert(head, Node(1))
# print linked list
printList(head)
Rearrange linked list in increasing order (Sort linked list)
Given a linked list, write a function to rearrange its nodes to be sorted in increasing order.
The idea is to use the sortedInsert() function to sort a linked list. We start with an empty result list. Iterate through the source list and sortedInsert() each of its nodes into the result list. Be careful to note the .next field in each node before moving it into the result list.
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to insert a given node at its correct sorted position into a given # list sorted in increasing order def sortedInsert(head, newNode):
dummy = Node()
current = dummy
dummy.next = head
while current.next and current.next.data < newNode.data:
current = current.next
newNode.next = current.next
current.next = newNode
return dummy.next
# Given a list, change it to be in sorted order (using `sortedInsert()`). def insertSort(head):
result = None # build the answer here current = head # iterate over the original list
while current:
# tricky: note the next reference before we change it
next = current.next
result = sortedInsert(result, current)
current = next
return result
if __name__ == ‘__main__’:
# input keys
keys = [6, 3, 4, 8, 2, 9]
# points to the head node of the linked list
head = None
# construct a linked list
for i in reversed(range(len(keys))):
head = Node(keys[i], head)
head = insertSort(head)
# print linked list
printList(head)
Split nodes of a linked list into the front and back halves
Given a linked list, split it into two sublists – one for the front half and one for the back half. If the total number of elements in the list is odd, the extra element should go in the front list.
Probably the simplest strategy is to compute the length of the list, then use a for loop to hop over the right number of nodes to find the last node of the front half, and then cut the list at that point.
_______________________________________-
# Return the total number of nodes in a list def findLength(head):
count = 0
ptr = head
while ptr:
count = count + 1
ptr = ptr.next
return count
’’’
Split the given list’s nodes into front and back halves,
and return the two lists using a list.
If the length is odd, the extra node should go in the front list.
‘’’
def frontBackSplit(source):
length = findLength(source)
if length < 2:
frontRef = source
backRef = None
return frontRef, backRef
current = source
hopCount = (length - 1) // 2 # figured these with a few drawings
for i in range(hopCount):
current = current.next
# Now cut at current
frontRef = source
backRef = current.next
current.next = None
return frontRef, backRef
if __name__ == ‘__main__’:
# input keys
keys = [6, 3, 4, 8, 2, 9]
# points to the head node of the linked list
head = None
Probably the simplest strategy is to compute the length of the list, then use a for loop to hop over the right number of nodes to find the last node of the front half, and then cut the list at that point.
# construct a linked list
for i in reversed(range(len(keys))):
head = Node(keys[i], head)
first, second = frontBackSplit(head)
# print linked list
printList('Front List: ', first)
printList('Back List: ', second)
Remove duplicates from a sorted linked list
Given a linked list sorted in increasing order, write a function that removes duplicate nodes from it by traversing the list only once.
# Remove duplicates from a sorted list def removeDuplicates(head):
# do nothing if the list is empty
if head is None:
return None
current = head
# compare the current node with the next node
while current.next:
if current.data == current.next.data:
nextNext = current.next.next
current.next = nextNext
else:
current = current.next # only advance if no deletion
return head
if __name__ == ‘__main__’:
# input keys
keys = [1, 2, 2, 2, 3, 4, 4, 5]
# construct a linked list
head = None
for i in reversed(range(len(keys))):
head = Node(keys[i], head)
head = removeDuplicates(head)
# print linked list
printList(head)
Move even nodes to the end of the linked list in reverse order
Rearrange a given linked list such that every even node will be moved to the end of the list in reverse order.
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list. The auxiliary space required by the program is constant.
______________________________
class Node:
def \_\_init\_\_(self, data = None, next = None):
self.data = data
self.next = next
def printlist(head):
ptr = head
while ptr:
print(ptr.data)
ptr = ptr.next
def move_even(head):
new_node = Node()
if head is None:
return
prev =None
lst_even = []
current = head
while current :
if current.data%2 ==0:
lst_even.append(current.data)
prev.next = current.next
prev = current
current = current.next
##- cunstructing new node
for i in (lst_even):
new_node= Node(i, new_node)
prev.next = new_node return head
if __name__ == ‘__main__’:
Split a linked list into two lists where each list contains alternating elements from it
Given a linked list of integers, split it into two lists containing alternating elements from the original list.
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to print a given linked list def printList(msg, head):
print(msg, end='')
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
’’’
Given the source list, split its nodes into two shorter lists.
If we number the elements 0, 1, 2, then all the even elements
should go in the first list and all the odd elements in the second.
The elements in the lists may be in any order.
‘’’
def alternatingSplit(source):
# Split the nodes into `a` and `b` lists
a = None
b = None
current = source
while current:
# Move a node to `a`
newNode = current # the front source node
current = current.next # advance the source
newNode.next = a # link the old dest off the new node
a = newNode # move dest to point to the new node
if current:
# Move a node to `b`
newNode = current # the front source node
current = current.next # advance the source
newNode.next = b # link the old dest off the new node
b = newNode # move dest to point to the new node
return a, b
if __name__ == ‘__main__’:
# construct the first linked list
head = None
for i in reversed(range(7)):
head = Node(i + 1, head)
first, second = alternatingSplit(head)
# print both lists
printList('First List: ', first)
printList('Second List: ', second)
dummy node techniques
it is start from:
dummy = Node()
tail = dummy –> this line is somehow making access to the head
so now on, you can use .next to add to this dummy node
Note that in return you need to return dummy.next
shuffle merge list
Construct a linked list by merging alternate nodes of two given lists
Given two linked lists, merge their nodes to make one list, taking nodes alternately between the two lists. If either list runs out, all the nodes should be taken from the other list.
The strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives tail something to point to initially when the result list is empty. This dummy node is efficient since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either a or b and adding it to tail. When we are done, the result is in dummy.next.
code##############
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(msg, head):
print(msg, end='')
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to construct a linked list by merging alternate nodes of # two given linked lists using a dummy node def shuffleMerge(a, b):
dummy = Node() tail = dummy
while True:
# empty list cases
if a is None:
tail.next = b
break
elif b is None:
tail.next = a
break
# common case: move two nodes to the tail
else:
tail.next = a
tail = a
a = a.next
tail.next = b
tail = b
b = b.next
return dummy.next
if __name__ == ‘__main__’:
a = b = None
for i in reversed(range(1, 8, 2)):
a = Node(i, a)
for i in reversed(range(2, 7, 2)):
b = Node(i, b)
# print both lists
printList('First List: ', a)
printList('Second List: ', b)
head = shuffleMerge(a, b)
printList('After Merge: ', head)
Merge two sorted linked lists into one
Write a function that takes two lists, each of which is sorted in increasing order, and merges the two into a single list in increasing order, and returns it.
For example, consider lists a = {1, 3, 5, 7} and b = {2, 4, 6}. Merging them should yield the list {1, 2, 3, 4, 5, 6, 7}.
1. Using Dummy Nodes The strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives the tail something to point to initially when the result list is empty. This dummy node is efficient since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either a or b and adding it at the tail. When we are done, the result is in dummy.next. ##################### code
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(msg, head):
print(msg, end='')
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Takes two lists sorted in increasing order and merge their nodes # to make one big sorted list, which is returned
def sortedMerge(a,b):
dummy = Node()
tail = dummy
while True:
if a is None:
tail.next = b
break
elif b is None:
tail.next =a
break
else:
if a.data <= b.data and a:
tail.next = a
tail =a
a = a.next
else:
tail.next = b
tail =b
b =b.next
return dummy.next
if __name__ == ‘__main__’:
a = b = None
for i in reversed(range(1, 8, 2)):
a = Node(i, a)
for i in reversed(range(2, 7, 2)):
b = Node(i, b)
# print both lists
printList(a)
printList( b)
head = sortedMerge(a, b) printList( head)
Intersection of two sorted linked lists
Given two lists sorted in increasing order, return a new list representing their intersection. The new list should be made with its own memory – the original lists should not be changed.
Input:
First List: 1 —> 4 —> 7 —> 10 —> null
Second List: 2 —> 4 —> 6 —> 8 —> 10 —> null
Output: 4 —> 10 —> null
The strategy is to advance up both lists and build the result list as we go. When the current point in both lists is the same, add a node to the result. Otherwise, advance whichever list is smaller. By exploiting the fact that both lists are sorted, we only traverse each list once.
code
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(msg, head):
print(msg, end='')
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Compute a new sorted list representing the intersection # of the two given sorted lists without using a dummy node def sortedIntersect(a, b):
head = tail = None
# once one or the other list runs out — we are done
while a and b:
if a.data == b.data:
if head is None:
head = Node(a.data, head)
tail = head
else:
tail.next = Node(a.data, tail.next)
tail = tail.next
a = a.next
b = b.next
# advance the smaller list
elif a.data < b.data:
a = a.next
else:
b = b.next
return head
if __name__ == ‘__main__’:
a = None
for i in reversed(range(1, 11, 3)):
a = Node(i, a)
b = None
for i in reversed(range(2, 11, 2)):
b = Node(i, b)
# print both lists
printList('First List: ', a)
printList('Second List: ', b)
head = sortedIntersect(a, b)
printList('After Intersection: ', head)
Reverse a linked List – Iterative Solution
The idea is to use three-pointers: next, current, previous and move them down the list. Here, current is the main pointer running down the list, next leads it, and previous trails it. For each step, reverse the current pointer and then advance all three to get the next node.
code##########
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Reverses a given linked list by changing its `.next` fields and # its head. def reverse(head):
previous = None current = head
# traverse the list
while current:
# tricky: note the next node
next = current.next
current.next = previous # fix the current node
previous = current
current = next
# fix the head to point to the new front
return previous
if __name__ == ‘__main__’:
head = None
for i in reversed(range(6)):
head = Node(i + 1, head)
head = reverse(head)
printList(head)
Reverse every group of k nodes in a linked list
Given a linked list, reverse every adjacent group of k nodes where k is a given positive integer.
The idea is to consider every group of k nodes and recursively reverse them one at a time. Special care has to be taken while linking reversed groups with each other
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print linked list starting from the current node
def print(self):
ptr = self
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to reverse every group of `k` nodes in a given linked list def reverseInGroups(head, k):
# base case
if head is None:
return None
# start with the current node
current = head
# reverse next `k` nodes
prev = None
count = 0
# iterate through the list and move/insert each node
# in front of the result list (like a push of the node)
while current and count < k:
count = count + 1
# tricky: note the next node
next = current.next
# move the current node onto the result
current.next = prev
# update the previous pointer to the current node
prev = current
# move to the next node in the list
current = next
# recur for remaining nodes
head.next = reverseInGroups(current, k)
# it is important to return the previous node (to link every group of `k` nodes)
return prev
if __name__ == ‘__main__’:
head = None
for i in reversed(range(8)):
head = Node(i + 1, head)
head = reverseInGroups(head, 3)
head.print()
Find k’th node from the end of a linked list
A simple solution is to calculate the total number of nodes n in the linked list first. Then, the k’th node from the end will be (n-k+1)’th node from the beginning.
code
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Iterative function to return the k'th node from the end in a linked list def getKthFromEnd(head, k):
n = 0 curr = head
# count the total number of nodes in the linked list
while curr:
curr = curr.next
n = n + 1
# if the total number of nodes is more than or equal to `k`
if n >= k:
# return (n-k+1)'th node from the beginning
curr = head
for i in range(n - k):
curr = curr.next
return curr
if __name__ == ‘__main__’:
head = None
for i in reversed(range(5)):
head = Node(i + 1, head)
k = 3
node = getKthFromEnd(head, k)
if node:
print('k\'th node from the end is', node.data)
Merge alternate nodes of two linked lists into the first list
Given two linked lists, merge their nodes into the first list by taking nodes alternately between the two lists. If the first list runs out, the remaining nodes of the second list should not be moved.
For example, consider lists {1, 2, 3} and {4, 5, 6, 7, 8}. Merging them should result in {1, 4, 2, 5, 3, 6} and {7, 8}, respectively.
The strategy here uses a temporary dummy node as the start of the result list. The pointer tail always points to the last node in the result list, so appending new nodes is easy. The dummy node gives the tail something to point to initially when the result list is empty. This dummy node is efficient since it is only temporary, and it is allocated in the stack. The loop proceeds, removing one node from either a or b and adding it to the tail. When we are done, set a to dummy.next.
The time complexity of all above-discussed methods is O(m + n), where m and n are the total number of nodes in the first and second list, respectively.
code
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to print a given linked list def printList(msg, head):
print(msg, end='')
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to construct a linked list by merging alternate nodes of # two given linked lists using a dummy node def merge(a, b):
dummy = Node() tail = dummy
while True:
# empty list cases
if a is None:
tail.next = None # Note
break
elif b is None:
tail.next = a
break
# common case: move two nodes to the tail
else:
tail.next = a
tail = a
a = a.next
tail.next = b
tail = b
b = b.next
a = dummy.next
return a, b
if __name__ == ‘__main__’:
a = b = None
# construct the first list
for i in reversed(range(4)):
a = Node(i, a)
# construct the second list
for i in reversed(range(4, 11)):
b = Node(i, b)
# print both lists
printList('First List: ', a)
printList('Second List: ', b)
a, b = merge(a, b)
print('\nAfter Merge:')
printList('First List: ', a)
printList('Second List: ', b
movenode() technique
which takes the node from the front of the source and moves it to the front of the destination
1) define : result = None then through a while loop you do: pick the first node like a new_node = a a = a.next new_node.next = results result = new_node
Merge two sorted linked lists from their end
Write a function that takes two lists, each of which is sorted in increasing order, and merges the two into one list, which is in decreasing order, and returns it. In other words, merge two sorted linked lists from their end.
For example, consider lists a = {1, 3, 5} and b = {2, 6, 7, 10}. Merging both lists should yield the list {10, 7, 6, 5, 3, 2, 1}.
There are few cases to deal with – either a or b may be empty, during processing, either a or b may run out first, and finally, there’s the problem of starting the result list empty, and building it up while going through a and b.
We can easily solve this problem using the moveNode() function as a helper, which takes the node from the front of the source and moves it to the front of the destination. The rest of the code remains similar to the merge process of merge sort.
def reverseMerge(a, b):
result = None
while a and b:
if a.data < b.data:
# take the node from the front of the list `a`, and move it
# to the front of the result
newNode = a
a = a.next
newNode.next = result
result = newNode
else:
# take the node from the front of the list `b`, and move it
# to the front of the result
newNode = b
b = b.next
newNode.next = result
result = newNode
while b:
newNode = b
b = b.next
newNode.next = result
result = newNode
while a:
newNode = a
a = a.next
newNode.next = result
result = newNode
return result
if __name__ == ‘__main__’:
a = b = None
for i in reversed(range(2, 8, 2)):
a = Node(i, a)
for i in reversed(range(1, 10, 2)):
b = Node(i, b)
# print both lists
printList('First List: ', a)
printList('Second List: ', b)
head = reverseMerge(a, b)
printList('After Merge: ', head)
Delete every N nodes in a linked list after skipping M nodes
Given a linked list and two positive integers, m and n, delete every n nodes after skipping m nodes.
The idea is to traverse the given list, skip the first m nodes, delete the next n nodes, and recur for the remaining nodes. The solution is simple, but we need to ensure that all boundary conditions are handled properly in the code.
######### code
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Recursive function to delete every `n` nodes in a linked list after # skipping `m` nodes def deleteNodes(head, m, n):
# base case
if head is None or head.next is None:
return head
prev = None curr = head
# skip `m` nodes
for i in range(1, m + 1):
prev = curr
curr = curr.next
# return if we have reached end of the list
if not curr:
return head
# delete next `n` nodes
for i in range(1, n + 1):
if curr:
next = curr.next
curr = next
# link remaining nodes with the last node
prev.next = curr
# recur for remaining nodes
deleteNodes(curr, m, n)
return head
if __name__ == ‘__main__’:
head = None
for i in reversed(range(10)):
head = Node(i + 1, head)
head = deleteNodes(head, 1, 3)
printList(head)
find middle of a linked list and retur if it is an odd number
# Function to split the linked list into two equal parts and return the # pointer to the second half def findMiddle(head, odd):
prev = None slow = head fast = head
# find the middle pointer
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# for odd nodes, `fast` still points to the last node
if fast:
odd = True
# make next of previous node None
prev.next = None
# return middle node
return slow, odd
Check if a linked list is palindrome or not
We can solve this problem in constant space and linear time by dividing the problem into three subproblems:
Divide the list into two equal parts.
Reverse the second half.
Check if the first and second half is similar. If the linked list contains an odd number of nodes, then ignore the middle element.
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Iterative function to reverse nodes of a linked list def reverse(head):
result = None current = head
# Iterate through the list and move/insert each node
# in front of the result list (like a push of the node)
while current:
# tricky: note the next node
nextNode = current.next
# move the current node onto the result
current.next = result
result = current
# process next node
current = nextNode
# fix head pointer
head = result
return head
# Recursive function to check if two linked lists are equal or not def compare(a, b):
# see if both lists are empty
if a is None and b is None:
return True
return a and b and (a.data == b.data) and compare(a.next, b.next)
# Function to split the linked list into two equal parts and return the # pointer to the second half def findMiddle(head, odd):
prev = None slow = head fast = head
# find the middle pointer
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# for odd nodes, `fast` still points to the last node
if fast:
odd = True
# make next of previous node None
prev.next = None
# return middle node
return slow, odd
# Function to check if the linked list is a palindrome or not def checkPalindrome(head):
# base case
if head is None or head.next is None:
return True
# flag to indicate if the total number of nodes in the linked list is
# odd or not.
odd = False
# find the second half of the linked list
mid, odd = findMiddle(head, odd)
# if the total number of nodes is odd, advance mid
if odd:
mid = mid.next
# reverse the second half
mid = reverse(mid)
# compare the first and second half
return compare(head, mid)
if __name__ == ‘__main__’:
# input keys
keys = [1, 2, 3, 2, 1]
head = None
for i in reversed(range(len(keys))):
head = Node(keys[i], head)
if checkPalindrome(head):
print('The linked list is a palindrome')
else:
print('The linked list is not a palindrome')
In place shuffle merge
def shuffleMerge(a, b):
# see if either list is empty
if a is None:
return b
if b is None:
return a
# it turns out to be convenient to do the recursive call first;
# otherwise, `a.next` and `b.next` need temporary storage
recur = shuffleMerge(a.next, b.next) result = a # one node from `a` a. next = b # one from `b` b. next = recur # then the `rest` return result
Rearrange linked list in a specific manner in linear time
Given a linked list, rearrange its nodes such that alternate positions are filled with nodes starting from the beginning and end of the list. in linear time and constant space.
Input : 1 —> 2 —> 3 —> 4 —> 5 —> 6
Output: 1 —> 6 —> 2 —> 5 —> 3 —> 4
We can easily solve this problem by dividing it into three subproblems:
Divide the list into two equal parts.
Reverse the second half.
Merge the second half into the first half at alternate positions. Use of extra space is not allowed (Not allowed to create additional nodes), i.e., insertion must be done in-place.
O(N) time
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Iterative function to reverse nodes of a linked list def reverse(head):
result = None current = head
# Iterate through the list and move/insert each node
# in front of the result list (like a push of the node)
while current:
# tricky: note the next node
next = current.next
# move the current node onto the result
current.next = result
result = current
# process next node
current = next
# fix head pointer
return result
# Recursive function to construct a linked list by merging # alternate nodes of two given linked lists def shuffleMerge(a, b):
# see if either list is empty
if a is None:
return b
if b is None:
return a
# it turns out to be convenient to do the recursive call first;
# otherwise, `a.next` and `b.next` need temporary storage
recur = shuffleMerge(a.next, b.next) result = a # one node from `a` a. next = b # one from `b` b. next = recur # then the `rest` return result
# Function to split the linked list into two equal parts and return the # pointer to the second half def findMiddle(head):
prev = None slow = fast = head
# find the middle pointer
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
# for odd nodes, fix middle
if fast and fast.next is None:
prev = slow
slow = slow.next
# make next of previous node None
prev.next = None
# return middle node
return slow
# Function to rearrange given linked list in a specific way def rearrange(head):
# base case
if head is None:
return
# find the second half of the linked list
mid = findMiddle(head)
# reverse the second half
mid = reverse(mid)
# merge first and second half
shuffleMerge(head, mid)
if __name__ == ‘__main__’:
head = None
for i in reversed(range(6)):
head = Node(i + 1, head)
rearrange(head)
printList(head)
Move the last node to the front of a linked list
For example, list {1, 2, 3, 4} should be changed to {4, 1, 2, 3}
The idea is to make the linked list circular and then break the chain before the last node after making its head to point to the last node.
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Helper function to print a given linked list def printList(head):
ptr = head
while ptr:
print(ptr.data, end=' —> ')
ptr = ptr.next
print('None')
# Function to move the last node to the front of a given linked list def rearrange(head):
# proceed only when the list is valid
if head is None or head.next is None:
return head
ptr = head
# move to the second last node
while ptr.next.next:
ptr = ptr.next
# transform the list into a circular list
ptr.next.next = head
head = ptr.next # Fix head ptr.next = None # break the chain return head
if __name__ == ‘__main__’:
# 1 —> 2 —> 3 —> 4 —> None
head = None
for i in reversed(range(4)):
head = Node(i + 1, head)
head = rearrange(head) printList(head)
return the last second node
def last_second_Node (head):
if head is None or head.next is None:
return head
ptr = head
while ptr.next.next:
ptr = ptr.next
return ptrDetect cycle in a linked list (Floyd’s Cycle Detection Algorithm)
- Using Hashing
A simple solution is to use hashing. The idea is to traverse the given list and insert each encountered node into a set. If the current node already presents in the set (i.e., it is seen before), that means a cycle is present in the list.
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list. The auxiliary space required by the program is O(n).
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to detect a cycle in a linked list using hashing def detectCycle(head):
curr = head s = set()
# traverse the list
while curr:
# return false if we already have seen this node before
if curr in s:
return True
# insert the current node into the set
s.add(curr)
# move to the next node
curr = curr.next
# we reach here if the list does not contain any cycle
return False
if __name__ == ‘__main__’:
head = None
for i in reversed(range(5)):
head = Node(i + 1, head)
# insert cycle
head.next.next.next.next.next = head.next.next
if detectCycle(head):
print('Cycle Found')
else:
print('No Cycle Found')
_________________
2. Floyd’s Cycle Detection Algorithm
Floyd’s cycle detection algorithm is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds. The idea is to move the fast pointer twice as quickly as the slow pointer, and the distance between them increases by one at each step. If we both meet at some point, we have found a cycle in the list; otherwise, no cycle is present if the end of the list is reached. It is also called the “tortoise and the hare algorithm”.
The time complexity of the above solution is O(n), where n is the total number of nodes in the linked list, and doesn’t require any extra space.
# A Linked List Node
class Node:
def \_\_init\_\_(self, data=None, next=None):
self.data = data
self.next = next
# Function to detect a cycle in a linked list using # Floyd’s cycle detection algorithm def detectCycle(head):
# take two references – `slow` and `fast`
slow = fast = head
while fast and fast.next:
# move slow by one
slow = slow.next
# move fast by two
fast = fast.next.next
# if they meet any node, the linked list contains a cycle
if slow == fast:
return True
# we reach here if slow and fast do not meet
return False
if __name__ == ‘__main__’:
head = None
for i in reversed(range(5)):
head = Node(i + 1, head)
# insert cycle
head.next.next.next.next.next = head.next.next
if detectCycle(head):
print('Cycle Found')
else:
print('No Cycle Found')
