Snippets Collections
# 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]:
        dummy = ListNode(0, head)
        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]:
    	if head is None: 
            return []
        elif head.next is None and n == 1: 
            return []
        else: 
            current = head
            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 
            previous, current = head, head 
            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

            return head 











# //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 

class DoublyLinkedList:
  def __init__(self, head=None, tail=None, length=0):
    self.head = head 
    self.tail = tail 
    self.length = length 

  #add to end of list 
  def append(self, value): 
    new_node = Node(value)
    #if there is no head (list is empty), set head and tail to be new_node 
    if self.head == None: 
      self.head = 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): 
    if self.head == None: 
      return None 
    #current will eventually be the last elemeent and will be removed 
    current = self.head 
    #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.head = None
      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): 
    if self.head == None: 
      return None 
    #current_head will be removed and returned 
    current_head = self.head 
    self.head = current_head.next 
    #severs new self.head previous property
    self.head.previous = None 
    self.length -= 1 
    #to account when list will be destroyed 
    if self.length == 0: 
      self.tail = None 
    #severs current_head. Note previous is already set to None 
    current_head.next = None 
    return current_head 

  
  #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 
    if self.head == None: 
      self.head = new_node 
      self.tail = self.head 
    else: 
      temp = self.head 
      self.head = new_node 
      self.head.next = temp 
      temp.previous = self.head 
    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 
    current = self.head 
    #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 
      #unlink removed_node 
      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): 
    #switching head and tail 
    current = self.head 
    self.head = self.tail 
    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 
  def print_linkedlist_to_list(self): 
    result = []
    current = self.head 
    while current: 
      result.append(current.value)
      current = current.next 
    print(result)
    
    
    

# l = DoublyLinkedList() 
# 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.print_linkedlist_to_list()
# l.reverse() 
# l.print_linkedlist_to_list()

# 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 

class SinglyLinkedList:
  def __init__(self, head=None, tail=None, length=0):
    self.head = head 
    self.tail = tail 
    self.length = length 

  #add to end of list 
  def append(self, value): 
    new_node = Node(value)
    #if there is no head (list is empty), set head and tail to be new_node 
    if self.head == None: 
      self.head = new_node 
      self.tail = self.head 
    #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): 
    if self.head == None: 
      return None 
    #current will eventually be the last elemeent and will be removed 
    current = self.head 
    #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.head = None
      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): 
    if self.head == None: 
      return None 
    current_head = self.head 
    self.head = current_head.next 
    self.length -= 1 
    #to account when list will be destroyed 
    if self.length == 0: 
      self.tail = None 
    return current_head 
  
  #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 
    if self.head == None: 
      self.head = new_node 
      self.tail = self.head 
    else: 
      temp = self.head 
      self.head = new_node 
      self.head.next = temp 
    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 
    current = self.head 
    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 
      #unlink removed_node 
      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): 
    #switching head and tail 
    current = self.head 
    self.head = self.tail 
    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 
  def print_linkedlist_to_list(self): 
    result = []
    current = self.head 
    while current: 
      result.append(current.value)
      current = current.next 
    print(result)
    
    
    

l = SinglyLinkedList() 
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.print_linkedlist_to_list()
l.reverse() 
l.print_linkedlist_to_list()

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 (Coordinated Universal Time) https://leetcode.com/problems/remove-nth-node-from-end-of-list/submissions/

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

Save snippets that work with our extensions

Available in the Chrome Web Store Get Firefox Add-on Get VS Code extension