Delete given node from linked list without head

Easy

We have a singly linked list. Our task is to delete a node from a singly-linked list. We will not be given access to the head of the list instead, We will be given access to the node to be deleted directly. It is guaranteed that the node to be deleted is not a tail node in the list.

 

Example

Input:

 Linked list: [1,4,2,3 ]  Node = 2

Output:

Linked list: [1,4,3]

 

Approach

We are given access to nodes that we have to delete from the linked list. So, whatever operation we want to do in the linked list, we can operate in the right part of the linked list from the node to be deleted.

The approach is to copy the next node’s value in the deleted node. Then, link the node to next of next node. This does not delete that node but indirectly it removes that node from the linked list.

 

Complexity

  • Time Complexity: O(1)
  • Space Complexity : O(1)

 

Code

# Java Code

import java.util.*;

class LinkedListNoHead {

    static class Node {
        int num;
        Node next;

        Node(int a) {
            num = a;
            next = null;
        }
    }

    // Function to insert a node at the end of the list
    static Node insertNode(Node head, int val) {
        Node newNode = new Node(val);
        if (head == null) {
            head = newNode;
            return head;
        }
        Node temp = head;
        while (temp.next != null)
            temp = temp.next;
        temp.next = newNode;
        return head;
    }

    // Function to get reference of the node to delete
    static Node getNode(Node head, int val) {
        if (head == null)
            return null;
        while (head.num != val)
            head = head.next;
        return head;
    }

    // Delete function as per the question
    static void deleteNode(Node t) {
        if (t == null)
            return;
        t.num = t.next.num;
        t.next = t.next.next;
        return;
    }

    // Printing the list function
    static void printList(Node head) {
        if (head == null)
            return;
        while (head.next != null) {
            System.out.print(head.num + "->");
            head = head.next;
        }
        System.out.println(head.num);
    }

    public static void main(String args[]) {
        Node head = null;
        // Inserting nodes
        head = insertNode(head, 1);
        head = insertNode(head, 4);
        head = insertNode(head, 2);
        head = insertNode(head, 3);
        // Printing given list
        System.out.println("Given Linked List: ");
        printList(head);
        Node t = getNode(head, 2);
        // Delete node
        deleteNode(t);
        // List after deletion operation
        System.out.println("Linked List after deletion: ");
        printList(head);
    }
}
Output
Given Linked List: 
1->4->2->3
Linked List after deletion: 
1->4->3

 



Thanks for feedback.



Read More....
Find the no of islands in a 2D Array/Matrix
3 Sum
4 Sum - Find four elements that sum to a given target value
Chocolate Distribution Problem
Find the missing number in a sorted array
Best Time to Buy and Sell Stock