2.3 Delete Middle Node – CCI

  • Store value of next node to current node
  • Set next pointer of current node to the node after the next node
# [2.3] Delete Middle Node: Implement an algorithm to 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.

# Space complexity: O(1)
# Time complexity: O(N)

import unittest

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

def delete_middle_node(node):
    node.value = node.next.value
    node.next = node.next.next
class Test(unittest.TestCase):

    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)

    n1.next = n2
    n2.next = n3
    n3.next = n4
    n4.next = n5
    def test_delete_middle_node(self):


    def node_vals_to_list(self, node):
        result = []
        while node:
            node = node.next

        return result
if __name__ == '__main__':