1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 Θ. \$\endgroup\$ – greybeard Nov 6 at 7:26
  • \$\begingroup\$ 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. \$\endgroup\$ – greybeard Nov 6 at 7:26
  • \$\begingroup\$ 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. \$\endgroup\$ – greybeard Nov 6 at 8:02
0
\$\begingroup\$
  • 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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.