Posted on by Kalkicode
Code Single linked list

Delete all prime nodes from a Singly Linked List

The problem at hand is to delete all prime nodes from a singly linked list. A singly linked list is a linear data structure where each element, known as a node, holds a value and a reference to the next node in the sequence. In this case, we are dealing with a singly linked list of integers. The task is to identify and remove all nodes that contain prime numbers from the linked list.

Delete all prime number in Given linked list after Delete all prime number in Given linked list

Problem Statement

Given a singly linked list of integers, we need to delete all nodes that contain prime numbers.

Example

Consider the following linked list:

7 -> 1 -> 8 -> 2 -> 4 -> 23 -> 37 -> NULL

After deleting prime nodes, the list becomes:

1 -> 8 -> 4 -> NULL

Idea to Solve the Problem

To solve this problem, we can iterate through the linked list while checking each node's value for primality. If a prime node is found, we will remove it from the list. We can maintain three pointers: temp, hold, and prev. The temp pointer will traverse through the list, hold will keep track of the prime node to be removed, and prev will be used to adjust the references after removing nodes.

Algorithm

  1. Initialize temp as the head of the linked list and hold and prev as null.
  2. Iterate through the linked list using the temp pointer.
    • If the value of temp node is prime:
      • Set hold as temp to mark the prime node for removal.
    • Else:
      • Set prev as temp (since we need to keep track of the previous non-prime node).
    • Move temp to the next node.
  3. If hold is not null:
    • If hold is the head node:
      • Update the head to skip the prime node (i.e., set head as temp).
    • Else:
      • Update the next reference of the previous non-prime node to skip the prime node (i.e., set prev.next as temp).
  4. Repeat steps 2-3 until the end of the linked list is reached.
  5. The linked list will now contain only the non-prime nodes.

Pseudocode

function deletePrimeNodes():
    temp = head
    hold = null
    prev = null

    while temp is not null:
        if isPrime(temp.data):
            hold = temp
        else:
            prev = temp
        
        temp = temp.next
        
        if hold is not null:
            if hold is head:
                head = temp
            else:
                prev.next = temp
            hold = null

Code Solution

Time Complexity

The time complexity of the algorithm is determined by the traversal of the linked list. In the worst case, each node is visited once, resulting in a time complexity of O(n), where n is the number of nodes in the linked list.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment