Insert node into the middle of the linked list | Node class ; constructor to create a new node ; function to insert node at the middle of linked list given the head ; if the list is empty ; create a new node for the value to be inserted ; calcualte the length of the linked list ; ' count ' the number of node after which the new node has to be inserted ; move ptr to the node after which the new node has to inserted ; insert the ' newNode ' and adjust links accordingly ; function to displat the linked list ; Creating the linked list 1.2 . 4.5 ; inserting 3 in the middle of the linked list .
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def insertAtMid ( head , x ) : NEW_LINE INDENT if ( head == None ) : NEW_LINE INDENT head = Node ( x ) NEW_LINE DEDENT else : NEW_LINE INDENT newNode = Node ( x ) NEW_LINE ptr = head NEW_LINE length = 0 NEW_LINE while ( ptr != None ) : NEW_LINE INDENT ptr = ptr . next NEW_LINE length += 1 NEW_LINE DEDENT if ( length % 2 == 0 ) : NEW_LINE INDENT count = length / 2 NEW_LINE DEDENT else : NEW_LINE INDENT ( length + 1 ) / 2 NEW_LINE DEDENT ptr = head NEW_LINE while ( count > 1 ) : NEW_LINE INDENT count -= 1 NEW_LINE ptr = ptr . next NEW_LINE DEDENT newNode . next = ptr . next NEW_LINE ptr . next = newNode NEW_LINE DEDENT DEDENT def display ( head ) : NEW_LINE INDENT temp = head NEW_LINE while ( temp != None ) : NEW_LINE INDENT print ( str ( temp . data ) , end = " ▁ " ) NEW_LINE temp = temp . next NEW_LINE DEDENT DEDENT head = Node ( 1 ) NEW_LINE head . next = Node ( 2 ) NEW_LINE head . next . next = Node ( 4 ) NEW_LINE head . next . next . next = Node ( 5 ) NEW_LINE print ( " Linked ▁ list ▁ before ▁ insertion : ▁ " , end = " " ) NEW_LINE display ( head ) NEW_LINE x = 3 NEW_LINE insertAtMid ( head , x ) NEW_LINE print ( " Linked list after insertion : " ▁ , ▁ end ▁ = ▁ " " ) NEW_LINE display ( head ) NEW_LINE