```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
left = dummy
right = head #we actually want right to be head + n

#setting right to be head + n
while n > 0 and right:
right = right.next
n -= 1

#this should get left at previous and right at after thanks to dummy node we inserted
while right:
left = left.next
right = right.next

#delete node
left.next = left.next.next

return dummy.next

#bottom solution is what I first came up with and works in leetcode except for if head = [1] and n = 1 which is the case I tried to account for in the second elif statement but it gave me an error saying cannot return [] even though it was fine for the first if statement

#big O: is still O(n) just like 1st scenario

class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
return []
elif head.next is None and n == 1:
return []
else:
counter = 0 #will become length of LL

#to determine length of LL
while current is not None:
counter += 1
current = current.next

#consider adding an edge case here if n > counter

#second pass now knowing length of LL
new_counter = 0
target = counter - n
while new_counter is not target + 1:
if new_counter == (target - 1):
previous = current
if new_counter == target:
after = current.next
previous.next = after
current.next = None
break

current = current.next

new_counter += 1

```
```# //almost identical to doubly linked list but
# //every node has another pointer to previous node
# //Advantages: able to access list at end instead of going from start
# //Disadvantages: takes up more memory

class Node:
def __init__(self, value, next=None, previous=None):
self.value = value
self.next = next
self.previous = previous

self.tail = tail
self.length = length

def append(self, value):
new_node = Node(value)
#if there is no head (list is empty), set head and tail to be new_node
self.tail = new_node
#otheriwse, set next property on tail to be new node and set tail to be newly created node
else:
self.tail.next = new_node
new_node.previous = self.tail
self.tail = new_node
#increment length and return
self.length += 1
return self

#removes last element of list
def pop(self):
return None
#current will eventually be the last elemeent and will be removed
#variable right before end
new_tail = current
#while loop to traverse to end
while current.next:
new_tail = current
current = current.next
#sets new tail
self.tail = new_tail
#cuts off old tail and current previous property
self.tail.next = None
current.previous = None
#decrement list
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None
return current

#removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later
def shift(self):
return None
#current_head will be removed and returned
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None

#adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O
def unshift(self, value):
new_node = Node(value)
#edge case to account if list is originally empty
else:
self.length += 1

#travels to node at index and returns node
def traverse(self, index):
if index < 0 or index >= self.length:
raise IndexError('index out of range')
counter = 0
#since this is doubly linked list, you can also approach from tail and go backwards
while counter != index:
current = current.next
counter += 1
return current

#travels to node at index and returns node's value
def get(self, index):
#to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on
if index < 0:
index = self.length + index
node = self.traverse(index)
return node.value

#replaces value at index
def set(self, index, value):
found_node = self.traverse(index)
if found_node:
found_node.value = value
return True
else:
return False

#insert value at index and adds 1 to length, returns boolean if successful
def insert(self, index, value):
if index < 0 or index > self.length:
raise IndexError('index out of range')
if index == self.length:
#not not is similar to !! in javascript and it's so it returns a boolean if successful
return not not self.append(value)
if index == 0:
return not not self.unshift(value)
else:
new_node = Node(value)
previous_node = self.traverse(index - 1)
after_node = previous_node.next

#creating relations before new_node
previous_node.next = new_node
new_node.previous = previous_node
#creating relations after new_node
new_node.next = after_node
after_node.previous = new_node

#increment length
self.length += 1
return self

def remove(self, index):
if index < 0 or index > self.length:
return indexError('index out of range')
if index == self.length - 1:
return self.pop()
if index == 0:
return self.shift()
else:
#need to get previous node and after node to create relationships
previous_node = self.traverse(index - 1)
#removed_node will be removed and returned
removed_node = previous_node.next
after_node = removed_node.next
previous_node.next = removed_node.next
after_node.previous = previous_node
#sever removed_node next
removed_node.next = None
removed_node.previous = None
self.length -= 1
return removed_node

#common interview question
def reverse(self):
self.tail = current

next, previous = None, None
#to show for loop is possible in LL. Could use while loop as well
for i in range(0, self.length):
#think of this as creating the block
next = current.next
current.next = previous #initially None
current.previous = next
#think of this as connecting head/previous to the block
previous = current
current = next
return self

# # // [100. 201, 250, 350, 999]
# # // first part
# # // NODE  NEXT
# # // 100 -> null

# # // second part (for loop and beyond)
# # // PREV  NODE  NEXT
# # // line 154( prev = current; ) specifically:
# # // 201 -> 100  -> null
# # // line 155 (current = next;):
# # //        PREV  NODE  NEXT
# # // 250 -> 201 -> 100

#useful to visualize reverse() or any other function works
result = []
while current:
result.append(current.value)
current = current.next
print(result)

# l.append(1)
# l.append(2)
# l.pop()
# l.shift()
# l.unshift(3)
# l.append(4)
# l.traverse(0)
# l.get(-2)
# l.set(2, 7)
# l.insert(0, 99)
# l.remove(2)
# l.reverse()

# y = l.length
# print(y)

# // Insertion:
# // O(1)
# // Removal: recall in SL it depends
# // O(1)
# // Searching:
# // O(N) but optimized bc you can start from head or tail (but more memory)
# // Access:
# // Same as searching ```
```class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

self.tail = tail
self.length = length

def append(self, value):
new_node = Node(value)
#if there is no head (list is empty), set head and tail to be new_node
#otheriwse, set next property on tail to be new node and set tail to be newly created node
else:
self.tail.next = new_node
self.tail = self.tail.next
#increment length and return
self.length += 1
return self

#removes last element of list
def pop(self):
return None
#current will eventually be the last elemeent and will be removed
#variable right before end
new_tail = current
#while loop to traverse to end
while current.next:
new_tail = current
current = current.next
#sets new tail
self.tail = new_tail
#cuts off old tail
self.tail.next = None
#decrement list
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None
return current

#removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later
def shift(self):
return None
self.length -= 1
#to account when list will be destroyed
if self.length == 0:
self.tail = None

#adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O
def unshift(self, value):
new_node = Node(value)
#edge case to account if list is originally empty
else:
self.length += 1

#travels to node at index and returns node
def traverse(self, index):
if index < 0 or index >= self.length:
raise IndexError('index out of range')
counter = 0
while counter != index:
current = current.next
counter += 1
return current

#travels to node at index and returns node's value
def get(self, index):
#to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on
if index < 0:
index = self.length + index
node = self.traverse(index)
return node.value

#replaces value at index
def set(self, index, value):
found_node = self.traverse(index)
if found_node:
found_node.value = value
return True
else:
return False

#insert value at index and adds 1 to length, returns boolean if successful
def insert(self, index, value):
if index < 0 or index > self.length:
raise IndexError('index out of range')
if index == self.length:
#not not is similar to !! in javascript and it's so it returns a boolean if successful
return not not self.append(value)
if index == 0:
return not not self.unshift(value)
else:
new_node = Node(value)
previous_node = self.traverse(index - 1)
temp = previous_node.next
#set next property of previous node to be new_node
previous_node.next = new_node
#set new_node next to be old next of previous
#you can also write this as previous_node.next.next = temp
new_node.next = temp
self.length += 1
return True

def remove(self, index):
if index < 0 or index > self.length:
return indexError('index out of range')
if index == self.length - 1:
return self.pop()
if index == 0:
return self.shift()
else:
#need to get previous node to create relationships
previous_node = self.traverse(index - 1)
#removed_node will be removed and returned
removed_node = previous_node.next
previous_node.next = removed_node.next
#sever removed_node next
removed_node.next = None
self.length -= 1
return removed_node

#common interview question
def reverse(self):
self.tail = current

next, previous = None, None
#to show for loop is possible in LL. Could use while loop as well
for i in range(0, self.length):
#think of this as creating the block
next = current.next
current.next = previous #initially None
#think of this as connecting head/previous to the block
previous = current
current = next
return self

# // [100. 201, 250, 350, 999]
# // first part
# // NODE  NEXT
# // 100 -> null

# // second part (for loop and beyond)
# // PREV  NODE  NEXT
# // line 154( prev = current; ) specifically:
# // 201 -> 100  -> null
# // line 155 (current = next;):
# //        PREV  NODE  NEXT
# // 250 -> 201 -> 100

#useful to visualize reverse() works
result = []
while current:
result.append(current.value)
current = current.next
print(result)

l.push(1)
l.push(2)
l.pop()
l.shift()
l.unshift(3)
l.push(4)
l.traverse(0)
l.get(-2)
l.set(2, 7)
l.insert(0, 99)
l.remove(2)
l.reverse()

y = l.length
print(y)

# //Big O:
# //Insertion: O(1)
# //Removal: depends O(1) if start or O(N) at end
# //Above 2 are main advantages vs. arrays esp at start
# //Searching: O(N)
# //Access: O(N)

# //Recall with array implenetation, insertion and removal is not constant ```
star

Fri Aug 12 2022 20:01:25 GMT+0000 (UTC) https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/

#python #linked #list #two #pointer #dummy #node