DELETE Kth NODE FROM THE END

Concepts Used

Basics of linked list.

Difficulty Level

Easy

Problem Statement :

You are given a singly-linked list, delete the kth node from the end of the list and then print Linked list after deletion of the kthnode.

Note: Given k will be always valid.

EXAMPLE:

Given: 1->2->3->4->5->6
K=3

after deletion:
1->2->3->5->6

4 is the third last node from the end of linked list.

You are encouraged to try the problem on your own before looking at the solution.
See original problem statement here

EXPLANATION:

Brute force:

Start with the first node and count the number of nodes present after that node.If the number of nodes are
If the number of nodes are > K-1 then go to the next node.

Continue this until the number of nodes after current node are K-1.

Time complexity: O(n*n) ,for scanningthe remaining list (from current node) for each list.
Space complexity: O(1).

Can we make this any better?

Approach 2:

If L is the length of the linked list,(L−k+1) th node from the beginning is Kth node from the ned of the linked list.

Look at the example:

K=4;

You can see that the 4th node from the end is the same node which is 2nd from the beginning (L-K+1=5-4+1).

So the problem could be simply reduced to another one : Remove the (L−k+1) th node from the beginning in the list , where L is the list length. This problem becomes easy if we find the length of the list .

Time Complexity: O(n).

Space complexity: O(1).

Note: This algorithm needs two traversals(one to find L). The below algorithm is one pass algorithm.

Approach 3:

Use two pointers lKthNode and lTemp.Initially, both points to head node of the list.lKthNode starts moving only after lTemp made K moves.

From there both moves forward until lTemp reaches the end of the list. As a result lKthTemp points to the kth node from the end of the linked list.

Time Complexity: O(n).

Space complexity: O(1).

SOLUTIONS:

 #include <stdio.h>
    #include<stdlib.h>
     struct node{
     int data;
     struct node* next;
    };
      struct node* newnode(int x)
     {
     //struct node* temp=new node();
     struct node* temp;
     temp= (struct node *)malloc(sizeof(struct node));
     temp->data=x;
     temp->next=NULL;
     return temp;
     }
     int main()
    {
    int t;scanf("%d",&t);
     while(t--)
    {
    int n,k;scanf("%d%d",&n,&k);
    int x;scanf("%d",&x);
    struct node* head=newnode(x);
    struct   node* headlist=head;
    for(int i=1;i<n;i++)
    {
     int y;scanf("%d",&y);
     head->next=newnode(y);
     head=head->next;
    }
    struct node* prev=NULL,*current=headlist;
    for(int i=1;i<k;i++)
    {
     prev=current;
     current=current->next;
    }
    if(prev==NULL)
    {
     headlist=current->next;
    // delete(current);
    }
    else
    {
     struct node* nxt=current->next;
     prev->next=nxt;
     //delete(current);
    }
     while(headlist!=NULL)
    {
     printf("%d ",headlist->data);
      headlist=headlist->next;
    }
    printf("\n");
    }

    return 0;
    }
#include <bits/stdc++.h>
     using namespace std;
     struct node{
     int data;
     node* next;
    };
       node* newnode(int x)
     {
     node* temp=new node();
     temp->data=x;
     temp->next=NULL;
     return temp;
     }
     int main()
    {
    int t;cin>>t;
     while(t--)
    {
    int n,k;cin>>n>>k;
    int x;cin>>x;
    node* head=newnode(x);
    node* headlist=head;
    for(int i=1;i<n;i++)
    {
     int y;cin>>y;
     head->next=newnode(y);
     head=head->next;
    }
    node* prev=NULL,*current=headlist;
    for(int i=1;i<k;i++)
    {
     prev=current;
     current=current->next;
    }
    if(prev==NULL)
    {
     headlist=current->next;
     delete(current);
    }
    else
    {
     node* nxt=current->next;
     prev->next=nxt;
     delete(current);
    }
     while(headlist!=NULL)
    {
     cout<<headlist->data<<" ";
      headlist=headlist->next;
    }
    cout<<"\n";
    }

    return 0;
    }
import java.util.*;
     import java.io.*;

    class LinkedList 
    { 
    Node head; 
    class Node 
    { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
    public void push(int new_data) 
    { 
        Node new_node = new Node(new_data); 
        new_node.next = head; 

        head = new_node; 
    } 
    void deleteNode(int position) 
    { 
        if (head == null) 
            return;  
        Node temp = head; 
        if (position == 0) 
        { 
            head = temp.next; 
            return; 
        } 
        for (int i=0; temp!=null && i<position-1; i++) 
            temp = temp.next;  
        if (temp == null || temp.next == null) 
            return; 

        Node next = temp.next.next; 

        temp.next = next; 
    } 
    public void printList() 
    { 
        Node tnode = head; 
        while (tnode != null) 
        { 
            System.out.print(tnode.data+" "); 
            tnode = tnode.next; 
        } 
    } 
    public static void main(String[] args) 
    { 
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
        while(t-- >0 ){
            int n = sc.nextInt();
            int k = sc.nextInt();
        LinkedList llist = new LinkedList(); 
        int p[]=new int[n];
            for(int i=0;i<n;i++)
            {
                p[i] = sc.nextInt();
            }
        for(int i=n-1;i>=0;i--)
            {
                llist.push(p[i]); 
            }

        llist.deleteNode(k-1);  
        llist.printList(); }
    } 
     } 
class Node:
	def __init__(self, new_data):
		self.data = new_data
		self.next = None

class LinkedList:
	def __init__(self):
		self.head = None

	def push(self, new_data):
		new_node = Node(new_data)
		new_node.next = self.head
		self.head = new_node

	def deleteNode(self, n):
		first = self.head
		second = self.head
		for i in range(n):
			if(second.next == None):
				if(i == n - 1):
					self.head = self.head.next
				return self.head
			second = second.next
		
		while(second.next != None):
			second = second.next
			first = first.next
		
		first.next = first.next.next
	
	def printList(self):
		tmp_head = self.head
		while(tmp_head != None):
			print(tmp_head.data, end = ' ')
			tmp_head = tmp_head.next
		
llist = LinkedList()
llist.push(7)
llist.push(1)
llist.push(3)
llist.push(2)
print("Created Linked list is:")
llist.printList()
llist.deleteNode(1)
print("\nLinked List after Deletion is:")
llist.printList()



[forminator_quiz id="1499"]

This article tried to discuss linked list. Hope this blog helps you understand and solve the problem. To practice more problems on linked list you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *