LINK02P02 - Editorial

editorial
, ,
1

Problem Link - Insertion at end in Circular Linked List

Problem Statement:

Whenever inserting a new node, there can be two cases:

  1. The list is empty (head = null) - Simply assign both head and tail as the new node and update the next pointer of tail.

  2. The list is not empty

  • The new node is supposed to be added after tail, thus set next of tail to new node.
  • Update the tail to new node because now it is the last element.
  • Update the next of new tail to existing head.

Complete the insertAtEnd function in the IDE.

Approach:

The key idea of this solution is to maintain a circular linked list where the last node’s next pointer connects back to the first node (head). This ensures that traversing the list can form a loop. The insertion of new elements is done efficiently using the tail pointer.

Here’s how the approach works:

  1. Node Structure:

    • A Node stores two things:
      • value: The data of the node.
      • next: A pointer that points to the next node in the list.

  2. insertAtEnd(int value):

    • A new node is created using the provided value.
    • If the list is empty (head == NULL), the new node becomes both the head and tail.
    • Otherwise, the new node is added after the current tail.
    • The tail is updated to this new node.
    • The new tail is then linked back to the head to maintain the circular structure.

Time Complexity:

  • insertAtEnd: O(1) since we directly update the tail pointer and make the circular connection without needing to traverse the list.

Space Complexity:

  • O(n) where n is the number of nodes, since we are storing n nodes in the linked list.