Chapter 2. Singely Linked List#
class Node():
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def linkedListToList(head):
res = []
while head:
res.append(head.val)
head = head.next
return res
Build#
def build(A):
dummy = Node()
if not A:
return dummy.next
prev = dummy
for a in A:
cur = Node(a)
prev.next = cur
prev = cur
return dummy.next
# test
A = [1,2,3,4]
head = build(A)
print(linkedListToList(head))
[1, 2, 3, 4]
Traverse#
The traversal of a linked list is usually performed by moving pointers using node.next.
# Iterative implementation: preorder traversal
def traverse(head):
res = []
while head:
res.append(head.val)
head = head.next
return res
# Test
A = [1,2,3,4]
head = build(A)
print(traverse(head))
[1, 2, 3, 4]
# Recursive implementation: preorder traversal
def traverse(node):
if not node:
return []
# preorder code
val = [node.val]
# recursive call
next_val = traverse(node.next)
return val + next_val
# Test
A = [1,2,3,4]
head = build(A)
print(traverse(head))
[1, 2, 3, 4]
# Recursive implementation: postorder traversal -> reverse the values
def traverse_postorder(node):
# base
if not node:
return []
#
next_val = traverse_postorder(node.next)
val = [node.val]
return next_val+val
# Test
A = [1,2,3,4]
head = build(A)
traverse_postorder(head)
[4, 3, 2, 1]
Insertion#
A node can be added in three ways
At the front of the linked list -> \(O(1)\)
After a given node -> \(O(1)\)
At the end of the linked list -> \(O(n)\)
def insertFront(head, val):
# construct a node
node = Node(val)
# make the new node as head
node.next = head
return node
def insertAfter(head, previous_node, val):
"""Insert new node with val after given previous_ndoe in head"""
node = Node(val)
tail = previous_node.next
previous_node.next = node
node.next = tail
return head
def insertEnd(head, val):
"""Insert to the end of a singley linked list"""
node = Node(val)
if not head:
return node
# traverse to the end
tail = head
while tail and tail.next:
tail = tail.next
# point to the new node
tail.next = node
return head
# test
# insert front
A = [1,2,3,4]
head = build(A)
val = 5
head = insertFront(head, val)
print(traverse(head))
# insert after
A = [1,2,3,4]
head = build(A)
val = 5
previous_node = head.next.next # 3
head = insertAfter(head, previous_node, val)
print(traverse(head))
# insert end
A = [1,2,3,4]
head = build(A)
val = 5
head = insertEnd(head, val)
print(traverse(head))
[5, 1, 2, 3, 4]
[1, 2, 3, 5, 4]
[1, 2, 3, 4, 5]
Deletion#
Similary to insertion, we can delete a node from a linked list at three positions:
At the front of the linked list -> \(O(1)\)
After a given node -> \(O(1)\)
At the end of the linked list -> \(O(n)\)
Search#
Given a linked list and a key X in, the task is to check if X is present in the linked list or not.
# An iterative implementation
def search(head, val):
if not head:
return False
while head:
if head.val == val:
return True
head = head.next
return False
#
A = [1,2,3,4]
head = build(A)
val = 5
print(search(head, val))
val = 2
print(search(head, val))
False
True
Indexing#
Find the
nth node from the beginning of a linked listFind the
nth node from the end of a linked listNaive implementation: N from the end is (lengh - N + 1) from beginning
Two-pointer:
the idea is to maintain two pointers starting from the head of the Linked-List and move one pointer to the Nth node from the start and then move both the pointers together until the pointer at the Nth position reaches the last node. Now the pointer which was moved later points at the Nth node from the end of the Linked-List
Find the middle node
Tow pointer: slow and fast pointer
def getNFromBegin(head, n):
if n < 1:
return -1
while head and n:
prev = head
head = head.next
n -= 1
# out of bound: n is greater than the length of the list
if not head and n > 0:
return -1
return prev.val
A = [1,10,30,14]
head = build(A)
n = 1
print(getNFromBegin(head, n))
n = 2
print(getNFromBegin(head, n))
n = 3
print(getNFromBegin(head, n))
n = 4
print(getNFromBegin(head, n))
n = 5
print(getNFromBegin(head, n))
1
10
30
14
-1
# Naive implementation: an iterative implementation
# time - O(n)
# space - O(1)
def getNFromEnd(head, n):
# get lenght of the list
l = 0
node = head
while node:
l += 1
node = node.next
# return -1 if out of bounds
if n > l: return -1
# get the (l-n+1) node from beginning
m = l-n+1
node = head
while m:
prev = node
node = node.next
m -= 1
return prev.val
A = [1,10,30,14]
head = build(A)
n = 1
print(getNFromEnd(head, n))
n = 2
print(getNFromEnd(head, n))
n = 3
print(getNFromEnd(head, n))
n = 4
print(getNFromEnd(head, n))
n = 5
print(getNFromEnd(head, n))
14
30
10
1
-1
## TODO: This is a wrong implementation - How to fix it?
# A recursive implementation
# time - O(n)
# space - O(n) due to recursive stack call
def getNFromEnd(head, n):
# get lenght of the list
l = 0
node = head
while node:
l += 1
node = node.next
# recursive calls
global i
i = 0
def helper(head, n, l):
global i
#print(i)
if not head:
return
if i==n:
return head.val
helper(head.next, n, l)
i += 1
return helper(head, n, l)
A = [1,10,30,14]
head = build(A)
n = 1
print(getNFromEnd(head, n))
n = 2
print(getNFromEnd(head, n))
n = 3
print(getNFromEnd(head, n))
n = 4
print(getNFromEnd(head, n))
n = 5
print(getNFromEnd(head, n))
None
None
None
None
None
# A two-pointer implementation
def getNFromEnd(head, n):
# get lenght of the list
l = 0
node = head
while node:
l += 1
node = node.next
# special case
if n > l:
return -1
def nextN(node, n):
if not node:
return
tmp = node
while n > 0 and tmp:
tmp = tmp.next
n -= 1
return tmp
left, right = head, nextN(head, n)
# move till right pointer reaches the end
while right:
left = left.next
right = right.next
return left.val
A = [1,10,30,14]
head = build(A)
n = 1
print(getNFromEnd(head, n))
n = 2
print(getNFromEnd(head, n))
n = 3
print(getNFromEnd(head, n))
n = 4
print(getNFromEnd(head, n))
n = 5
print(getNFromEnd(head, n))
14
30
10
1
-1
def getMiddle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
#
A = [1,10,30,14]
head = build(A)
mid = getMiddle(head)
print(mid.val)
A = [1,10,30,14, 15]
head = build(A)
mid = getMiddle(head)
print(mid.val)
30
30
Loops in Linked List#
Cycle Dection#
Detect if a linked list has a loop.
Method 1: Hash Map
idea
traverse the linked list
use a hash map to store the node that has been seen
if the coming node has already in the hash map, then there is a loop
complexity
time: O(n)
space: O(n)
Method 2: Floyd’s Cycle Finding Algorithm
idea
initiate a slow pointer and a fast pointer
iteratively, slow pointer moves one step, and fast pointers move two steps
when slow pointer is equal to fast pointer, then there is a loop
def cycleDetection(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# no loop
print(cycleDetection(node1))
# add a loop
node5.next = node2
print(cycleDetection(node1))
False
True
Cycle Entrance#
Find the cycle entrance, i.e., the common node, if there is a cycle in the linked list.
def findCycleEntrance(head):
# check if there is a cycle
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
# if there is no cycle, return -1
if not (fast and fast.next):
return -1
# has a cycle
# set slow to head, move slow and fast at the same speed
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
# no loop
print(findCycleEntrance(node1))
# add a loop
node5.next = node2
print(findCycleEntrance(node1).val)
-1
2
Length of Cycle#
Find the length of a cycle
Idea
we can find the cycle entrance first
then traverse the cycle till the entrance again.
Sort Linked List#
to-be added
Reverse Linked List#
Reverse a given linked list
iterative
recurisive: see https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/di-gui-mo–1eaae/
Leetcode
Reverse the Whole List#
# iterative implementation
def reverseSinglyLinkedList(head):
p = head
prev = None
while p:
tail = p.next
p.next = prev
prev = p
p = tail
return prev
A = [1,10,30,14]
head = build(A)
reverse = reverseSinglyLinkedList(head)
print(traverse(reverse))
[14, 30, 10, 1]
# recursive implementation
def reverseSinglyLinkedList(head):
# base
if not head or not head.next:
return head
# main recursion
reverse = reverseSinglyLinkedList(head.next)
head.next.next = head
head.next = None
return reverse
A = [1,10,30,14]
head = build(A)
reverse = reverseSinglyLinkedList(head)
print(traverse(reverse))
[14, 30, 10, 1]
Reverse the First N Nodes#
# An iterative implementation
def reverseN(head, n):
if n == 1:
return head
prev = None
curr = head
i = 1
while i <= n:
tail = curr.next
curr.next = prev
prev = curr
i += 1
curr = tail
# connect with tail
head.next = tail
return prev
A = [1,10,30,14]
head = build(A)
reverse = reverseN(head, 2)
print(traverse(reverse))
[10, 1, 30, 14]
# A recursive implementation
def reverseN(head, n):
# base case
if n == 1:
return head
newhead = reverseN(head.next, n - 1)
tail = head.next.next
head.next.next = head
head.next = tail
return newhead
A = [1,10,30,14]
head = build(A)
new = reverseN(head, 2)
print(traverse(new))
[10, 1, 30, 14]
Reverse the M to N nodes#
move head to the m node
reverse the first (n-m) node
# A recursive implementation
def reverseSinglyLinkedList(head, m, n):
# move to the m-1 node
head_m = head
i = 1
while i < m-1:
head_m = head_m.next
i += 1
# reverse the first n-m+1 nodes
# from the m mode
tail = head_m.next
print(head_m.val, tail.val)
i = 1
while i <= n - m + 1:
# n+1 node
tail = tail.next
i += 1
def reverse(head, n):
if n == 1:
return head
newhead = reverse(head.next, n - 1)
head.next.next = head
head.next = tail
return newhead
# connect together
rev = reverse(head_m.next, n - m + 1)
head_m.next = rev
return head
A = [1,10,30,14]
head = build(A)
new = reverseSinglyLinkedList(head, 2, 3)
print(traverse(new))
1 10
[1, 30, 10, 14]
# Recursive Implementation
def reverseFromMToN(head, m, n):
# base case: if m=1, then reverse the first N
if m == 1:
return reverseN(head, n)
# recursive call
tail = reverseFromMToN(head.next, m-1, n-1)
head.next = tail
return head
# test
A = [1,10,30,14]
head = build(A)
new = reverseFromMToN(head, 2, 3)
print(traverse(new))
A = [1,2, 3, 4, 5]
head = build(A)
new = reverseFromMToN(head, 2, 4)
print(traverse(new))
[1, 30, 10, 14]
[1, 4, 3, 2, 5]
Check Palindrome#
Method 1: Stack
traverse the list, and push every visited node to stack
traverse the list again. for every visited node,
pop a node from the stack
compare the data of the popped node and the currently visited node.
if all nodes match, then return true, else false
Method 2:
find the middle node
reverse the second half of the list
check if the reversed half list is equal to the first half of the original list
Intersection Node of Two Lists#
Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.
Note Dummy node is very good for creating a new linked list.
Input:
First linked list: 1->2->3->4->6
Second linked list be 2->4->6->8,
Output: 2->4->6.
The elements 2, 4, 6 are common in
both the list so they appear in the
intersection list.
Input:
First linked list: 1->2->3->4->5
Second linked list be 2->3->4,
Output: 2->3->4
The elements 2, 3, 4 are common in
both the list so they appear in the
intersection list.
def intersect1(l1, l2):
"""
This method changes the original data
"""
dummy = Node()
tail = dummy
p1, p2 = l1, l2
while p1 and p2:
if p1.val == p2.val:
tail.next = p1
tail = tail.next
p1 = p1.next
p2 = p2.next
elif p1.val < p2.val:
p1 = p1.next
elif p1.val > p2.val:
p2 = p2.val
return dummy.next
# test
l1 = [1,2,3,4,6]
l1 = build(l1)
l2 = [2,4,6,8]
l2 = build(l2)
intersection = intersect1(l1, l2)
print(traverse(intersection))
print(traverse(l1))
print(traverse(l2))
[2, 4, 6]
[1, 2, 4, 6]
[2, 4, 6, 8]
def intersect2(l1, l2):
"""
This method doesnt change the original data
"""
dummy = Node()
tail = dummy
p1, p2 = l1, l2
while p1 and p2:
if p1.val == p2.val:
newnode = Node(p1.val)
tail.next = newnode
tail = tail.next
p1 = p1.next
p2 = p2.next
elif p1.val < p2.val:
p1 = p1.next
elif p1.val > p2.val:
p2 = p2.val
return dummy.next
# test
l1 = [1,2,3,4,6]
l1 = build(l1)
l2 = [2,4,6,8]
l2 = build(l2)
intersection = intersect2(l1, l2)
print(traverse(intersection))
print(traverse(l1))
print(traverse(l2))
[2, 4, 6]
[1, 2, 3, 4, 6]
[2, 4, 6, 8]
Merge/Divide Lists#
Leetcode
[]