Leetcode: Linked Lists

Question 1

Add two numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Answer 1

Loop through both, add values to list, create a list to int and add them, then create a linked list from the values is brute.

1. Can be done in-line
2. Requires a carry variable to account for 6+8=14, the 1 needs to be carried to the next iteration
3. The new linked list must be created in reverse order. this requires a previous variable=None to start and it will be similar to how you reverse a linked list
4. The new node needs to be created with the remainder of the carry (modulus)

Time: Linear O(max(n1, n2))
Space: Linear O(max(n1, n2))

class Solution:

• —def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
• ——-current = response = ListNode(0)
• ——-carry = 0
• ——-while l1 or l2:
• —————carry += l1.val
• —————l1 = l1.next
• ———–if l2:
• —————carry += l2.val
• —————l2 = l2.next
• ———–div, mod = divmod(carry, 10)
• ———–carry = div
• ———–current.next = ListNode(mod)
• ———–current = current.next
• ——-if carry > 0:
• ———–current.next = ListNode(carry)
• ——-return response.next

Question 2

Find the intersection of linked list

You are given two singly linked lists. The lists intersect at some node. Find, and return the node. Note: the lists are non-cyclical.

Example:

A = 1 -> 2 -> 3 -> 4
B = 6 -> 3 -> 4

Answer 2

1. intersection of the linked list means that the nodes are of equal value,
   1-2- 3 -4
   /
   6
2. calculate lengths of linked lists
3. if one is larger than the other, increment through the linked list until they are the same size, for i in range(l1-l2), n1=n1.next
4. loop through each linked list and check if the nodes are equal, cannot check on value bc if a node is null you get npe

time: O (n1+n2)
space: O 1, we do not store any new values, we only change the head pointer of n1 or n2

def get_length(self, node):

• -if not node:
• —return 0
• -else:
• —return 1+self.get_length(node.next)

def optimal(self, n1, n2):

• -l1, l2 = self.get_length(n1), self.get_length(n2)
• -cur_1, cur_2 = n1, n2
• —if l1>l2:
• —–for i in range(l1-l2):
• ——-cur_1=cur_1.next
• —else:
• —–for i in range(l2-l1):
• ——-cur_2=cur_2.next
• —while cur_1 != cur_2:
• —–cur_1=cur_1.next
• —–cur_2=cur_2.next
• —return cur_1

Question 3

Consecutive nodes sum to 0

Hi, here’s your problem today. This problem was recently asked by Uber:

Given a linked list of integers, remove all consecutive nodes that sum up to 0.

Example:
Input: 10 -> 5 -> -3 -> -3 -> 1 -> 4 -> -4
Output: 10

The consecutive nodes 5 -> -3 -> -3 -> 1 sums up to 0 so that sequence should be removed. 4 -> -4 also sums up to 0 too so that sequence should also be removed.

Answer 3

1. can be solved by finding prefix sum if l1+l2 = l1+l2+…+l5, meaning that l3 + … + l5 = 0, then l3 + … + l5 is the consecutive sequence of nodes we want to delete.
2. If it’s a array we could just remove numbers from index of l3 to l5.
3. If it’s a linked list, we could let l2.next = l5.next, we then need to have two pointers, one point to l2 and the other point to l5
4. if you do not create a dummy head with .next=first value, then you should realize thatmore:
   Intuition and Algorithm
   Imagine that you have this Linked list:
   head: [3,4,2,-6, 1,1,5, -6]What elements should I remove?
   We will accumulate the values.
   head’ : [3, 7,9,3,4,5,10,4]
   (Like an array), head’[i] = head[i] + head’ [i-1]
   If we see repeated elements then we have to deleted as follows.

time: O(n), 2n because we loop through the linked list twice
space: O(n), worst-case we store all the values in the map

class Solution:

• —def very_difficult(self, node):
• ——-dummy_head=start = Node(0, node)
• ——-map={}
• ——-sum=0
• ——-while start:
• ———–sum+=start.value
• ———–map[sum]=start
• ———–start=start.next
• ——-start=dummy_head
• ——-sum=0
• ——-while start:
• ———–sum+=start.value
• ———–start.next=map[sum].next
• ———–start=start.next
• ——-return dummy_head.next

Question 4

list strategies for linked lists

Answer 4

1. linked lists go in circles if they are circular they loop around eventually (think of a fast/slow runner on a track)
2. Know how to swap 2 node in a position, you need temp variables and such (swap nodes in pairs)
3. fast/slow node using while fast and fast.next is a very common idea
4. Think of kth element from end, that is a way to get a fixed depth on a linked list without knowing the length
5. think of linked list with random pointer problem

Question 5

merge two sorted lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Answer 5

brute force is recursive, it will take O(n+m) time and space because of the recursive calls

• —def recursive(self, l1, l2):
• ——-if not l1:
• ———–return l2
• ——-elif not l2:
• ———–return l1
• ——-if l1.val < l2.val:
• ———–l1.next=self.recursive(l1.next, l2)
• ———–return l1
• ——-else:
• ———–l2.next=self.recursive(l1, l2.next)
• ———–return l2

1. Iterative is better for space
2. very similar to merge sort
3. while both ll’s are not none, we compare the heads and set the current.next value to the node that has the lesser value, and increment
4. once one of them is none, it means the remaining ll is sorted and we can set current.next = head of the last ll, creating the sorted list
5. return head.next

time: O(n+m), we traverse both ll’s fully
space: constant

• —def answer(self, l1: ListNode, l2: ListNode) -> ListNode:
• ——-current=head=ListNode(0)
• ——-while l1 and l2:
• ———–if l1.val less than l2.val:
• —————current.next = l1
• —————current=current.next
• —————l1=l1.next
• ———–else:
• —————current.next=l2
• —————current=current.next
• —————l2=l2.next
• ——-# to get this, you probably have to visualize it and write it out
• ——-current.next = l1 if l1 else l2
• ——-return head.next

Question 6

Linked list cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

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. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false

Answer 6

brute is to use a hashmap, but you can reduce the space complexity

• —def base(self, node):
• ——-m={}
• ——-current=node
• ——-while current:
• ———–if current in m:
• —————return True
• ———–m[current]=True
• ———–current=current.next

——–return False

1. how can we traverse a linked list? normally with next, or with a fast/slow with slow.next, fast.next.next
2. if the ll is a cycle, slow.next will eventually equal fast.next.next
3. first iteration we must check slow.next vs fast.next.next, or just make sure not to check the first nodes against each other bc they will be equal

time: O(2n), if it’s not cyclic it is just N, if it is it would be 2n to account for the slow iterations catching up with the fast ones. thinking about a fast/slow runner, the slow run would make 2 laps before they meet
space: constant, we create no new objects

class Solution:

• —def is_cyclic(self, node):
• ——-slow=fast=node
• ——-while slow and fast and fast.next:
• ———–if slow.next is fast.next.next:
• —————return True
• ———–slow=slow.next
• ———–fast=fast.next.next
• ——-return False
• —def recursive(self, head: Node) -> bool:
• ——-if not head or not head.next:
• ———–return False
• ——-return self.helper(head, head)
• —def helper(self, slow, fast):
• ——-if not slow or not fast or not fast.next:
• ———–return False
• ——-if slow.next is fast.next.next:
• ———–return True
• ——-elif self.helper(slow.next, fast.next.next):
• ———–return True

Question 7

Remove Kth element

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Answer 7

brute force is to calculate length of list with 1 pass, create the current=dummy=node(0, head), then subtract length-index to figure out when we stop traversing the list to delete the node. This takes at most 2 passes

1. single pass knowing that if we are 3 from the end, if we create 2 pointers, pointer a starts 3 ahead of the pointer b, when pointer a reaches the end, b will be at the pointer 3 from the end
2. when we have to do things in 1 pass, we typically need multiple pointers to the same object and we need to modify them in different ways, for linked lists, fast/slow
3. cannot return head bc when we remove the first node, head will still equal the first node, we need to make a dummy head and return dummy.next
   REMEMBER when you need to skip over a node, it is better to do node.next = node.next.next instead of doing node.next = other.next bc we know for a fact we can skip over the node doing node.next.next (I got it wrong in this problem bc I did slow.next = fast.next, but that doesn’t work in all cases)

time: linear, 1 pass, 2 pointers
space, constant

class Solution:

• —def answer(self, head, n):
• ——-dummy_head = ListNode(0, head)
• ——-slow = fast = dummy_head
• ——-for _ in range(n):
• ———–fast = fast.next
• ——-while fast and fast.next:
• ———–slow = slow.next
• ———–fast = fast.next
• ——-slow.next = slow.next.next
• ——-return dummy_head.next

1. takes 2 iterations

• —def removeNthFromEnd(self, head, n):
• ——-def get_length(node):
• ———–count = 0
• ———–while node:
• —————count += 1
• —————node = node.next
• ———–return count
• ——-l = get_length(head)
• ——-if l == n:
• ———–return head.next
• ——-prev = None
• ——-cur = head
• ——-for _ in range(l - n):
• ———–prev = cur
• ———–cur = cur.next
• ——-prev.next = cur.next
• ——-return head

Question 8

swap nodes in pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

Answer 8

1. recursive is develop a base case, make sure head and head.next are valid, and swap the nodes
2. iterative is the same, but we need to start off with an initial case and then do a while loop

time: O(n), linear,
space: recursive is linear bc of recursive space, iterative is constant space

class Solution:

• —def swapPairs(self, head: ListNode):
• ——-if not head or not head.next:
• —————return head
• ——-first=head
• ——-second=head.next
• ——-third=head.next.next
• ——-second.next=first
• ——-first.next=self.swapPairs(third)
• ——-return second
• —def iterative(self, head):
• ——-if not head or not head.next:
• —————return head
• ——-dummy_head=Node(0, head)
• ——-current=dummy_head.next
• ——-prev=dummy_head
• ——-while current and current.next:
• ———–first=current
• ———–second=current.next
• ———–third=second.next
• ———–second.next=first
• ———–first.next=third
• ———–prev.next=second
• ———–current=third
• ———–prev=first
• ——-return dummy_head.next

Question 9

Palindrome linked list

determine if a linked list is a palindrome

1, 2, 2, 1
1, 2, 3, 2, 1
1, 1, 1, 2, 3, 1,

Answer 9

1. to get to a midpoint of a linked list, perform slow=fast=node, while fast and fast.next. you need fast and fast.next bc on even linked lists, fast.next is valid but it will equal None, so None.next = NPE
2. slow points to the middle, the reverse of the middle will be equal to the current during a while loop for both, so while slow, check if current!=slow, if true return False, if not True
3. for recursive, we have to make sure each previous if/else statement is invalid when we hit the next one. the second if statement will change slow.next, which can affect the fast.next loop since we are changing the same objects in memory. we need to add if slow and fast and fast.next to prevent this, bc if slow==None, we won’t have the first or second if loop

time: O(n/2 + n/2 + n/2), we loop through half the node to get to the middle with slow, reverse slow, compare slow to current
space: constant, we do not create any additional objects

class Palindrome(object):

• —def answer(self, node):
• ——-slow=fast=current=node
• ——-while fast and fast.next:
• ———–fast=fast.next.next
• ———–slow=slow.next
• ——-slow=self.reverse(slow)
• ——-while slow:
• ———–if slow.value!=current.value:
• —————return False
• ———–slow=slow.next
• ———–current=current.next
• ——-return True
• —def reverse(self, node):
• ——-prev=None
• ——-while node:
• ———–_next=node.next
• ———–node.next=prev
• ———–prev=node
• ———–node=_next
• ——-return prev

Question 10

Convert Binary Search Tree to Sorted Doubly Linked List

Convert a Binary Search Tree to a sorted Circular Doubly-Linked List in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

Answer 10

brute is to do inorder traversal to create a list, create the circular dll with that list

1. can create circular dll with 1 loop using first/current pointers
2. when node.left == None, that root is the first value, so set that to first if first==None
3. then set current=root, which equals first
4. else, current.right=root, root.left=current, then swap current for root
5. dont forget to call inorder(root.right)!
6. at the end, connect the list, first.left=current, current.right=first, return first
7. you are modifying the original tree nodes, but we only modify root.left if there is no root.left and we do not modify root.right, so we can still traverse root.right

time: O(n), we traverse the whole tree and create the dll in 1 pass
space: O(N) the recursion depth, Log(n) if it is balanced

class Node:

• —def __init__(self, val, left=None, right=None):
• ——-self.val = val
• ——-self.left = left
• ——-self.right = right

class Solution:

• —def treeToDoublyList(self, root: ‘Node’) -> ‘Node’:
• ——-if not root:
• ———–return None
• ——-self.first, self.current = None, None
• ——-self.inorder(root)
• ——-self.current.right=self.first
• ——-self.first.left=self.current
• ——-return self.first
• —def inorder(self, root):
• ——-if root:
• ———–self.inorder(root.left)
• ———–if not self.first:
• —————self.first=root
• ———–else:
• —————self.current.right = root
• —————root.left = self.current
• ———–self.current=root
• ———–self.inorder(root.right)
• —def custom(self, root: ‘Node’) -> ‘Node’:
• ——-if not root:
• ———–return None
• ——-node_list=[]
• ——-self.inorder(root, node_list)
• ——-head = self.create_ll(node_list)
• ——-return head
• —def inorder(self, root, node_list):
• ——-if root:
• ———–self.inorder(root.left, node_list)
• ———–node_list.append(root.val)
• ———–self.inorder(root.right, node_list)
• —def create_ll(self, node_list):
• ——-_next=None
• ——-current=head=None
• ——-for x in node_list:
• ———–if not head:
• —————head = Node(x)
• —————current=head
• ———–else:
• —————current.right=Node(x, left=current)
• —————current=current.right
• ——-current.right=head
• ——-head.left=current
• ——-return head

Question 11

create a circular doubly linked list

Answer 11

class Node:

• —def __init__(self, data):
• ——-self.data = data
• ——-self.next = None
• ——-self.prev = None

# Function to insert at the end
def insertEnd(value) :
----global start
----
----# If the list is empty, create a
----# single node circular and doubly list
----if (start == None) :

• ——-new_node = Node(0)
• ——-new_node.data = value
• ——-new_node.next = new_node.prev = new_node
• ——-start = new_node
• ——-return

—-# If list is not empty

• —# Find last node */
• —last = (start).prev
• —# Create Node dynamically
• —new_node = Node(0)
• —new_node.data = value
• —# Start is going to be next of new_node
• —new_node.next = start
• —# Make new node previous of start
• —(start).prev = new_node
• —# Make last previous of new node
• —new_node.prev = last
• —# Make new node next of old last
• —last.next = new_node

# Function to insert Node at the beginning
# of the List,
def insertBegin( value) :
----global start
----
----# Pointer points to last Node
----last = (start).prev

• —new_node = Node(0)
• —new_node.data = value # Inserting the data
• —# setting up previous and
• —# next of new node
• —new_node.next = start
• —new_node.prev = last
• —# Update next and previous pointers
• —# of start and last.
• —last.next = (start).prev = new_node
• —# Update start pointer
• —start = new_node

# Function to insert node with value as value1.
# The new node is inserted after the node with
# with value2
def insertAfter(value1, value2) :
----global start
----new_node = Node(0)
----new_node.data = value1 # Inserting the data

• —# Find node having value2 and
• —# next node of it
• —temp = start
• —while (temp.data != value2) :
• ——-temp = temp.next
• —next = temp.next
• —# insert new_node between temp and next.
• —temp.next = new_node
• —new_node.prev = temp
• —new_node.next = next
• —next.prev = new_node

def display() :

• —global start
• —temp = start
• —print (“Traversal in forward direction:”)
• —while (temp.next != start) :
• ——-print (temp.data, end = “ “)
• ——-temp = temp.next
• —print (temp.data)
• —print (“Traversal in reverse direction:”)
• —last = start.prev
• —temp = last
• —while (temp.prev != last) :
• ——-print (temp.data, end = “ “)
• ——-temp = temp.prev
• —print (temp.data)

Question 12

copy list with random pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.
Your code will only be given the head of the original linked list.

Answer 12

iterative/recursive brute force involve a hashmap with the key being the real node and the value being the copy node. Check if the node already exists, if it does return it, else make one and return it. Both are linear time and space. For recursive problem remember to watch for cycles and think of it like a binary tree

Questions:
Can you modify the original input? will the input always be of class Node? can the random pointers point to the same node? will there be nodes with duplicate values?

1. need to find a way to relate the original.random to the new.random, but the random values are not guaranteed to be in any order
2. we must modify the original list by interweaving the original list with the new list
3. we need node1 - node1* - node2 - node2*
4. we create the weaved linked list with 1 while loop just using the nexts, then a second while loop to set the copy.random = current.random.next since each original.next points to its respective copy value, we can find the copy.random value in constant time
5. we can unweave this in the same while loop if we are very careful, but we can also just do 3 while loops for each step

time: O(n), we loop through the original list and copy list
space: constant,

class Solution:

• —def optimal(self, head):
• ——-if not head:
• ———–return None
• ——-current = head
• ——-copy_head = copy_current = None
• ——-while current:
• ———–if not copy_head:
• —————copy_head = copy_current = Node(current.val)
• ———–else:
• —————copy_current = Node(current.val)
• ———–_next = current.next
• ———–current.next = copy_current
• ———–copy_current.next = _next
• ———–current = current.next.next
• ——-current = head
• ——-copy_current = copy_head
• ——-while current:
• ———–if current.random:
• —————copy_current.random = current.random.next
• ———–else:
• —————copy_current.random = None
• ———–current = current.next.next
• ———–if current:
• —————copy_current.next = copy_current.next.next
• ———–else:
• —————copy_current.next = None
• ———–copy_current = copy_current.next
• ——-return copy_head
• —def remakes_input(self, head):
• ——-if not head:
• ———–return None
• ——-copy_head = copy = None
• ——-cur = head
• ——-while cur:
• ———–if not copy_head:
• —————copy_head = copy = Node(cur.val)
• ———–else:
• —————copy = Node(cur.val)
• ———–hold = cur.next
• ———–cur.next = copy
• ———–copy.next = hold
• ———–cur = hold
• ——-cur = head
• ——-copy = copy_head
• ——-while cur:
• ———–if cur.random:
• —————copy.random = cur.random.next
• ———–else:
• —————copy.random = None
• ———–if copy.next:
• —————copy = copy.next.next
• ———–cur = cur.next.next
• ——-cur = head
• ——-copy = copy_head
• ——-while cur:
• ———–cur.next = cur.next.next
• ———–if copy.next:
• —————copy.next = copy.next.next
• ———–copy = copy.next
• ———–cur = cur.next
• ——-return copy_head

Question 13

Design a linked list

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Answer 13

add at head is constant, the rest are linear time.

1. the difficult part here is indexing each different operation. get you need to make sure the index > size - 1, add at index checks index > size, if either are true we stop
2. make sure to increment/decrement the size at each add and delete operation
3. when doing test caes, test on a linked lith with 0 - 1 - 2, bc that does everything you need

class ListNode:

• —def __init__(self, x):
• ——-self.val = x
• ——-self.next = None

class MyLinkedList:

• —def __init__(self):
• ——-self.size = 0
• ——-self.head = ListNode(0)
• —def get(self, index: int) -> int:
• ——-if index > self.size - 1:
• ———–return -1
• ——-cur = self.head.next
• ——-for _ in range(index):
• ———–cur = cur.next
• ——-return cur.val
• —def addAtHead(self, val: int) -> None:
• ——-self.addAtIndex(0, val)
• —def addAtTail(self, val: int) -> None:
• ——-self.addAtIndex(self.size, val)
• —def addAtIndex(self, index: int, val: int) -> None:—-
• ——-if index > self.size:
• ———–return
• ——-cur = self.head.next
• ——-prev = self.head
• ——-for _ in range(index):
• ———–prev = cur
• ———–cur = cur.next
• ——-new = ListNode(val)
• ——-prev.next = new
• ——-new.next = cur
• ——-self.size += 1
• —def deleteAtIndex(self, index: int) -> None:
• ——-if index > self.size - 1:
• ———–return
• ——-cur = self.head.next
• ——-prev = self.head
• ——-for _ in range(index):
• ———–prev = cur
• ———–cur = cur.next
• ——-prev.next = cur.next
• ——-self.size -= 1

class MyLinkedList:

• —def __init__(self):
• ——-self.head = ListNode(0)
• —def get(self, index: int) -> int:
• ——-index += 1
• ——-cur = self.head
• ——-while index > 0 and cur:
• ———–cur = cur.next
• ———–index -= 1
• ——-return -1 if not cur else cur.val
• —def addAtHead(self, val: int) -> None:
• ——-hold = self.head.next
• ——-_new = ListNode(val)
• ——-self.head.next = _new
• ——-_new.next = hold
• —def addAtTail(self, val: int) -> None:
• ——-cur = self.head
• ——-prev = None
• ——-while cur:
• ———–prev = cur
• ———–cur = cur.next
• ——-prev.next = ListNode(val)
• —def addAtIndex(self, index: int, val: int) -> None:
• ——-if index == 0:
• ———–self.addAtHead(val)
• ——-else:
• ———–index += 1
• ———–cur = self.head
• ———–prev = None
• ———–while index > 0 and cur:
• —————prev = cur
• —————cur = cur.next
• —————index -= 1
• ———–if index == 0:
• —————if not cur:
• ——————-prev.next = ListNode(val)
• —————else:
• ——————-_new = ListNode(val)
• ——————-prev.next = _new
• ——————-_new.next = cur——–
• —def deleteAtIndex(self, index: int) -> None:
• ——-if index == 0:
• ———–self.head = self.head.next
• ——-else:
• ———–index += 1
• ———–cur = self.head
• ———–while index > 0 and cur:
• —————prev = cur
• —————cur = cur.next
• —————index -= 1
• ———–if index == 0 and cur:
• —————prev.next = cur.next

Question 14

Design a doubly linked list

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.
void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
void addAtTail(int val) Append a node of value val as the last element of the linked list.
void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

Answer 14

1. think outside the box, make sure to utilize a size variable, don’t be dumb and use a while loop!
2. we can reduce linear operations by checking if it is larger than half the size, if it is, starting from the back is better
3. show off your developer skills, no need to retype addAtHeadl/tail code incorporate that into your addAtIndex code!

class ListNode:

• —def __init__(self, x, next = None, prev = None):
• ——-self.val = x
• ——-self.next = next
• ——-self.prev = prev

class MyLinkedList:

• —def __init__(self):
• ——-self.size = 0
• ——-self.head, self.tail = ListNode(0), ListNode(0)
• ——-self.head.next = self.tail
• ——-self.tail.prev = self.head
• —def get(self, index: int) -> int:
• ——-if index > self.size - 1:
• ———–return -1
• ——-if index > self.size // 2:
• ———–cur = self.tail
• ———–for _ in range(self.size - index):
• —————cur = cur.prev
• ———–return cur.val
• ——-else:
• ———–cur = self.head.next
• ———–for _ in range(index):
• —————cur = cur.next
• ———–return cur.val
• —def addAtHead(self, val: int) -> None:
• ——-self.addAtIndex(0, val)
• —def addAtTail(self, val: int) -> None:
• ——-self.addAtIndex(self.size, val)
• —def addAtIndex(self, index: int, val: int) -> None:—-
• ——-if index > self.size:
• ———–return
• ——-if index > self.size // 2:
• ———–cur = self.tail
• ———–for _ in range(self.size - index):
• —————cur = cur.prev
• ——-else:
• ———–cur = self.head.next
• ———–for _ in range(index):
• —————cur = cur.next
• ——-prev = cur.prev
• ——-new = ListNode(val)
• ——-prev.next = new
• ——-new.prev = prev
• ——-new.next = cur
• ——-cur.prev = new
• ——-self.size += 1
• —def deleteAtIndex(self, index: int) -> None:
• ——-if index > self.size - 1:
• ———–return
• ——-if index > self.size // 2:
• ———–cur = self.tail
• ———–for _ in range(self.size - index):
• —————cur = cur.prev
• ——-else:
• ———–cur = self.head.next
• ———–for _ in range(index):
• —————cur = cur.next
• ——-cur.prev.next = cur.next
• ——-cur.next.prev = cur.prev
• ——-self.size -= 1

Question 15

linked list cycle 2

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Answer 15

brute force is to use a hashmap

1. fast/slow pointers on steroids
2. once you find a cycle, you need a pointer to that intersection and the head, then increment them each by 1 point. This is somehow proven that they will intersect at some point
3. moral of the story is to try random things. You need to find a cycle, you get a pointer, the only other data point you have is the head, try double incrementing or single incrementing

time: O(n). finding the cycle takes linear time, a proof shows it is F + C - h where F are the nodes not in the cycle and C are nodes in the cycle. The second part will take linear time aswell
space: constant

class Solution:

• —def detectCycle(self, head):
• ——-cycle_node = self.find_cycle(head)
• ——-if cycle_node:
• ———–start = head
• ———–while start != cycle_node:
• —————start = start.next
• —————cycle_node = cycle_node.next
• ———–return start
• ——-else:
• ———–return None
• —def find_cycle(self, head):
• ——-cycle = False
• ——-slow = fast = head
• ——-while slow and fast and fast.next:
• ———–if slow.next == fast.next.next:
• —————return fast.next.next
• ———–slow = slow.next
• ———–fast = fast.next.next
• ——-return None

Question 16

remove linked list elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Answer 16

class Solution:

• —def removeElements(self, head, val):
• ——-dummy_head = ListNode(‘a’, head)
• ——-prev = dummy_head
• ——-cur = head
• ——-while cur:
• ———–if cur.val == val:
• —————prev.next = cur.next
• ———–else:
• —————prev = cur
• ———–cur = cur.next
• ——-return dummy_head.next

Question 17

flatten a multi-level doubly linked list

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

Example 1:

Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Output: [1,2,3,7,8,11,12,9,10,4,5,6]
Explanation: The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:

Answer 17

1. DFS!
2. write it out, see that you are simply replacing the .next with the .child, and you might need to do so recursively.
3. managing what comes out and what pointer you go to next is key, at first you would think you go from current to current.next even if you find a child, but you don’t, you go to the tail of that child bc current.next might be None!
4. remember to run many test case, a 3 layer list with nested child elements, elements with only child nodes, these edge cases are what kills you

time: O(n), you go through the entire list once
space: O(n), worst case each node has a child element and you have N recursive space

class Solution:

• —def flatten(self, head: ‘Optional[Node]’) -> ‘Optional[Node]’:
• ——-if not head:
• ———–return head
• ——-self.__flatten_helper(head)
• ——-return head
• —def __flatten_helper(self, root):
• ——-if not root:
• ———–return root
• ——-cur = root
• ——-while cur.next or cur.child:
• ———–if cur.child:
• —————hold = cur.next
• —————cur.next = cur.child
• —————cur.next.prev = cur
• —————cur.child = None
• —————tail = self.__flatten_helper(cur.next)
• —————tail.next = hold
• —————if hold:
• ——————-hold.prev = tail
• —————cur = tail
• ———–else:
• —————cur = cur.next
• ——-return cur

Question 18

insert into a sorted circular linked list

Given a Circular Linked List node, which is sorted in ascending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.

If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.

If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.

Answer 18

1. state machine, draw it out
2. pretty simple, if prev < insert < cur, then we insert! the end point when cur < prev, is where we check for adding on the end or before the beginning
3. ask to make sure all the nodes can’t be the same number, if they can be then you need to check an answer is valid. do this by checking in the while loop to see when you’ve reached the head, if you reach the head. you can do this multiple ways but make sure you dont fuck up and add it on the first loop!

time: O(n), we loop once at most!
space: O(1), no new data structures

class Solution:

• —def insert(self, head: Node, insertVal: int) -> Node:
• ——-if not head:
• ———–new = Node(insertVal)
• ———–new.next = new
• ———–return new
• ——-# this is not needed, bc we check for it later, but honestly it was good to have at the time before I realized
• ——-# the values could all be the same
• ——-if not head.next:
• ———–new = Node(insertVal)
• ———–head.next = new
• ———–new.next = head
• ———–return head
• ——-cur = head.next
• ——-prev = head
• ——-while True:
• ———–if cur.val >= prev.val:
• —————if prev.val <= insertVal <= cur.val:
• ——————-new = Node(insertVal)
• ——————-prev.next = new
• ——————-new.next = cur
• ——————-break
• ———–else:
• —————if prev.val <= insertVal or cur.val >= insertVal:
• ——————-new = Node(insertVal)
• ——————-prev.next = new
• ——————-new.next = cur
• ——————-break
• ———–if cur == head:
• —————new = Node(insertVal)
• —————prev.next = new
• —————new.next = cur
• —————break
• ———–prev = cur
• ———–cur = cur.next
• ——-return head

Question 19

rotate linked list

Given the head of a linked list, rotate the list to the right by k places.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

Answer 19

brute force would be making a hashmap or array, then doing something similar to reverse array

1. similar to rotate array, but the reverse + partial reverse offers way too many edge cases and is extremely complicated. It can work, but dont do it
2. reverse array used a swap technique that involved true_rotations, total length, and modulus operator, this is very similar

time: O(n), we rotate through the list once, then again bc of the rotations
space: O(1)

class Solution:

• —def rotateRight(self, head, k):
• ——-if not head or not head.next:
• ———–return head
• ——-old_tail = head
• ——-length = 1
• ——-while old_tail.next:
• ———–old_tail = old_tail.next
• ———–length += 1
• ——-old_tail.next = head
• ——-true_rotations = k % length
• ——-for _ in range(length - true_rotations):
• ———–old_tail = old_tail.next
• ——-new_head = old_tail.next
• ——-old_tail.next = None
• ——-return new_head

Question 20

23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Answer 20

1. This solution is very difficult to come across, not intuitive by any means
2. the idea is to merge 2 lists together in steps, and continue until we can’t anymore
3. this requires interval to start at 1, while interval < len(lists), we also need to do a range loop with specific steps
4. very difficult to understand, but something you can work through if you test with 5 nodes and you can see it working.
5. 3 things to remember, interval < len, range(len - interval), step interval * 2, each while loop interval *= 2

time: O(n * logk) bc we merge the N nodes log(k) times where k is the len of lists
space: O(1), a slight improvement over my priority queue method

class Solution:

• —def optimal(self, lists):
• ——-if not lists:
• ———–return None
• ——-interval = 1
• ——-while interval < len(lists):
• ———–for i in range(0, len(lists) - interval, interval * 2):
• —————lists[i] = self.mergeTwo(lists[i], lists[i + interval])
• ———–interval *= 2
• ——-return lists[0]
• —def mergeTwo(self, n1, n2):
• ——-head = cur = ListNode(-1)
• ——-while n1 and n2:
• ———–if n1.val < n2.val:
• —————cur.next = n1
• —————n1 = n1.next
• ———–else:
• —————cur.next = n2
• —————n2 = n2.next
• ———–cur = cur.next
• ——-if not n1:
• ———–cur.next = n2
• ——-else:
• ———–cur.next = n1
• ——-return head.next

Custom solution, space is not truly optimal.

1. sorted, so we know the smallest value of each is the head
2. we can’t use list pointers on each list bc we don’t know how many we start with, when they end, or when to stop counting a pointer when it ends
3. perfect example of BFS! use a priority queue!!!!
4. if the head is not None, add the first element of each item to a priority queue
5. cast the values to a comparator(value, current, current.next) and make sure the __lt__ method returns true if they are equal. If we get 1 < 1, it will try to compare the ListNodes which is bad, each item needs to be deterministic on the val property
6. heapq.heappop the smallest value, cur.nxt = node, cur=cur.next, check if _next is valid and if so push it onto the queue.

time: O(n log K), where K is the number of linked lists and N is the total nodes. The heapq is kept at k length bc we never add more than k values to it and we do it N times.
space: O(K) where k is the number of linked lists

import heapq
class Solution:
----def mergeKLists(self, lists):
--------if not lists:
------------return None
--------
--------dummy_head = cur = ListNode(-1)
--------
--------queue = []
--------for head in lists:
------------if head:
----------------heapq.heappush(queue, Comparator(head.val, head, head.next))
--------
--------while queue:
------------comparator = heapq.heappop(queue)
------------val, node, _next = comparator.val, comparator.cur, comparator._next
------------cur.next = node
------------cur = cur.next
------------if _next:
----------------heapq.heappush(queue, Comparator(_next.val, _next, _next.next))
------------
--------return dummy_head.next
----
class Comparator:
----def \_\_init\_\_(self, val, cur, _next):
--------self.val = val
--------self.cur = cur
--------self._next = _next
--------
----def \_\_lt\_\_(self, y):
--------if self.val == y.val:
------------return True
--------else:
------------return self.val < y.val