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()
