Promoted
Promoted

## Linked List Operations - CheatSheet

This is a cheatsheet to review the Linked List data structure operations for the interview or system design. This will include approach, complexity followed by Python code for each operation. When is it appropriate to use Linked List in designing?

#### Cheat Sheet covers all Linked List Operations -

• Find mid-point of Linked List
1list

Linked List is a simple data structure that is made up of nodes. Each node has two components. One is the value and another is a pointer to the address of the next node. The next pointer of the last node of Linked List is NULL. Head is a pointer that points to the first node of Linked List.

3paragraph
4image

Below is python code to define Node

5paragraph
``` class Node: def __init__(self, val=0, next=None): self.val = val #Variable to store value self.next = next #Variable to address of next node```
6code

Promoted
Promoted

8image
• We use for loop, at each iteration we construct a node and update the next pointer of the previous node to the current node.
9list
``` def constructLinkedList(arr): if not arr: #If array is empty return NULL return #Create node from 1st element of array and make it head head = Node(val=arr[0]) #copy head to return it later as we should always return head of Linked List curr = head for i in range(1,len(arr)): #create node from ith element and assign it to next of curr element curr.next = Node(val=arr[i]) #make next node as current curr = curr.next return head #return head```
10code

#### Find a length of Linked List

• Check if head is NULL, if it is that mean Linked List length is 0.
• To find the length we need to loop through each node until we reach NULL. We use a variable named length which will increment as we traverse through nodes.
12list
``` def findLength(head): if not head: #if head is NULL return 0 return 0 length = 0 #init length to 0 while head: #run loop until head is NULL length+=1 #increment length head = head.next #make next node as head return length #return length```
13code

Promoted
Promoted

#### Find node in a Linked List

``` def findNode(head, key): if not head: #if head is NULL return -1 return -1 length = 0 #init length to 0 while head: #run loop until head is NULL #if key match value of head return length if head.val == key: return length length+=1 #increment length head = head.next #make next node as head return -1 #return -1, key not found```
15code

#### Insert node in a Linked List

``` def insertNode(head, pos, val): #if head is NULL and position is 0 #we create node and return it if not head and pos == 0: return Node(val) #if position is 0, add head to next of node created if pos == 0: node = Node(val) node.next = head return node #Track position length = 0 #Assign head curr = head #To store previous node prev = None #Run untill curr is NULL while curr: #if position match to length #create a node, assign next of prev as node #assign next of node as curr, return head if length == pos: node = Node(val) prev.next = node node.next = curr return head prev = curr curr = curr.next length+=1 #position is greater than length so no insertion return head```
17code

#### Delete node in a Linked List

``` def removeElements(head, key): if not head: return #Assign empty node to dummy dummy = Node(0) #Assign head as next node of dummy dummy.next = head #copy dummy to curr curr = dummy #Run a loop untill next of node of curr is NULL while curr.next: #If val of next node of curr match key #then skip next node by assigning #next to next node of curr to next node of curr if curr.next.val == key: curr.next = curr.next.next else: #else just move to next node curr = curr.next #return next node of dummy return dummy.next```
19code

Promoted
Promoted

``` def reverseList(head): #Assign NULL to prev prev = None #Assign head to curr curr = head #Run loop until curr is NULL while curr: #copy next of curr to next variable next = curr.next #assign prev to next node of curr curr.next = prev #make curr as prev prev = curr #make next as curr curr = next return prev ```
21code

#### Find mid-point of Linked List

``` def middleNode(head): #Assign head to fast fast = head #Run loop untill fast or next node of fast is NULL while fast and fast.next: #move head by one step head = head.next #move fast node by two step fast = fast.next.next #return head return head```
23code

#### Detect cycle in Linked List

``` def hasCycle(head): #if head is NULL if not head: return #Assign head to slow slow = head #Assign next node of head to fast fast = head.next #move fast pointer by 2 steps and slow by 1 step #untill fast or next node of fast or next to next node #of fast is NULL while fast and fast.next and fast.next.next: #if fast = slow, we found node if fast == slow: return True fast = fast.next.next slow = slow.next #we ran out of loop without finding cycle return False```
``` def mergeTwoLists(a, b): #Assign empty node to head and dummy head = dummy = Node(0) #Run loop untill we traversed all nodes from a and b while a or b: #incase we run out of nodes in b if a and not b: head.next = a a=a.next #incase we run out of nodes in a elif b and not a: head.next = b b=b.next #if b is smaller choose b elif a.val > b.val: head.next = b b=b.next #else choose else: head.next = a a=a.next #move head by one node head = head.next #return node next to dummy return dummy.next```