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