Make a Linked list
Calculate sum of a linked List
Add node to a linked list
def add_node(prev_node, node_to_add):
node_to_add.next= prev_node.next
prev_node.next= node_to_add
Delete a node from linked list
def delete_node(prev_node):
prev_node.next=prev_node.next.next
(1) Make a doubly linked list (2) add to end (3) remove from end (4) add to start (5) remove from start
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
def add_to_end(node_to_add):
node_to_add.next = tail
node_to_add.prev = tail.prev
tail.prev.next = node_to_add
tail.prev = node_to_add
def remove_from_end():
if head.next == tail:
return
node_to_remove = tail.prev node_to_remove.prev.next = tail tail.prev = node_to_remove.prev
def add_to_start(node_to_add):
node_to_add.prev = head
node_to_add.next = head.next
head.next.prev = node_to_add
head.next = node_to_add
def remove_from_start():
if head.next == tail:
return
node_to_remove = head.next node_to_remove.next.prev = head head.next = node_to_remove.next
head = ListNode(None)
tail = ListNode(None)
head.next = tail
tail.prev = head
(1) Make a doubly linked list (2) add node (3) delete node
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
Let node be the node at position i
def add_node(node, node_to_add):
prev_node = node.prev
node_to_add.next = node
node_to_add.prev = prev_node
prev_node.next = node_to_add
node.prev = node_to_add
Let node be the node at position i
def delete_node(node):
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
Example 1: Given the head of a linked list with an odd number of nodes head, return the value of the node in the middle.
For example, given a linked list that represents 1 -> 2 -> 3 -> 4 -> 5, return 3.
def get_middle(head):
length = 0
dummy = head
while dummy:
length += 1
dummy = dummy.next
for _ in range(length // 2):
head = head.next
return head.valOR The Smart way to add by Fast and Slow pointers
def get_middle(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow.val
Given the head of a linked list, determine if the linked list has a cycle.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Given the head of a linked list and an integer k, return the
k-th node from the end.
For example, given the linked list that represents 1 -> 2 -> 3 -> 4 -> 5 and k = 2, return the node with value 4, as it is the 2nd node from the end.
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
Reverse a linked list
Example: 24. Swap Nodes in Pairs
Given the head of a linked list, swap every pair of nodes. For example, given a linked list 1 -> 2 -> 3 -> 4 -> 5 -> 6, return a linked list 2 -> 1 -> 4 -> 3 -> 6 -> 5.
Reverse Linked List II
Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
Definition for singly-linked list.
