Teaching Kids Programming – Insert Into Linked List (Node Insertion Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a singly linked list head as well as integers pos and val. Insert a new node with value val before index pos of head.

Constraints
1 ≤ n ≤ 100,000 where n is the number of nodes in head
0 ≤ pos ≤ n

Example 1
Input
head = [1, 3, 5, 7]
pos = 2
val = 9
Output
[1, 3, 9, 5, 7]

Example 2
Input
head = [1]
pos = 0
val = 3
Output
[3, 1]

Example 3
Input
head = [2]
pos = 1
val = 5
Output
[2, 5]

Algorithm to Insert a Node into a Linked List

The node to insert may become a new head – thus we can create a dummy head and returns the next if necessary. The first step is to locate the place to insert, and we need to store its previous Node, so that we can redirect its next pointer to the newly created node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertNodeInLinkedList(self, head, pos, val):
        if not head:
            return LLNode(val)
        prev = dummy = LLNode(-1, head)
        for _ in range(pos):
            prev = head
            head = head.next
        prev.next = LLNode(val)
        prev.next.next = head
        return dummy.next

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertNodeInLinkedList(self, head, pos, val):
        if not head:
            return LLNode(val)
        prev = dummy = LLNode(-1, head)
        for _ in range(pos):
            prev = head
            head = head.next
        prev.next = LLNode(val)
        prev.next.next = head
        return dummy.next

Time complexity is O(N) as we are going through the nodes once. And the space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —