# Ruby: Remove middle node from Linked List

Currently, I'm going over the CTCI, I'm working on the problem removing the middle node. I'm using Ruby to go over these problems. I have the following solution.

 def remove_middle_node
node = @head
count = 1

while(node = node.next )
count += 1
end
# reset node to point to head
node = @head
middle = (count / 2)
count = 1

while(node = node.next)

if(count == (middle - 1))
node.next = node.next.next
return
end
count += 1
end
end


Instead of having a previos_node I subtract one from the middle. In this case when traversing the Linked List, when I get to the (middle - 1), meaning the previous node before the middle node in the linked list. I delete the middle node and set it to next.

I would like to get feedback on this implementation. In my understanding, this is O(n) and time complexity is also O(n). Although I warn you, this Big O notation still a bit unclear to me so time and space complexity might be wrong.

Here is the full Linked List class.

https://github.com/theasteve/ds_and_algos/blob/master/linked_list.rb here is the test I used.

# TEST
list = LinkedList.new

list.append(1)
list.append(2)
list.append(8)
list.append(3)
list.append(7)
list.append(0)
list.append(4)

list.display
puts '-----------------------------------'
list.remove_middle_node
list.display

• I don't get what this is in this is O(n) and time complexity is also O(n). Then, constant additional space would be in O(n) space as well as in O(1) space: if you think an upper bound to be tight, mention that or use Θ. – greybeard Nov 6 '19 at 7:26
• The wording of 2.3 Delete Middle Node is notably different: delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node. – greybeard Nov 6 '19 at 7:26
• I delete the middle node … I don't see that … and set it to next I see setting the predecessor's successor to the middle node's one. – greybeard Nov 6 '19 at 8:02

## 1 Answer

• document/comment your code. In the code.
• re-checking .next in the second loop is unusually defensive
• do not have a comment repeat what a statement "does" (reset node to point to head):
have it illuminate what is achieved/what-for/why something is done (the way it is)
• the ruby way to have a statement executed, say, middle times may be
middle.times do
node = node.next


(Eyeballing remove_middle_node, it uses O(1) additional space and Θ(n) time.)

• (One advantage of using a variable iterating the list half as fast would be the possibility to detect cycles and ensure termination.) – greybeard Nov 6 '19 at 8:22
• My Ruby was nothing to boast when it was best. – greybeard Dec 6 '19 at 9:26