Given a singly Linked List and an integer K denoting the position of a Linked List, the task is to delete the Kth node from the beginning and end of the Linked List.
Examples:
Input: 1 ? 2 ? 3 ? 4 ? 5 ? 6, K = 3
Output: 1 ? 2 ? 5 ? 6
Explanation: Deleted Nodes : 3, 4Input: 1 ? 2 ? 3 ? 4 ? 5 ? 6, K = 1
Output: 2 ? 3 ? 4 ? 5Input: 1 ? 2 ? 3 ? 4 ? 5 ? 6, K = 4
Output: 1 ? 2 ? 5 ? 6
Approach: Follow the steps to solve the problem
- Initialize two pointers fast and slow, to traverse the Linked List.
- Point both the nodes to the head of the Linked List.
- Iterate using fast pointer, until fast points to (K – 1)th node from the beginning.
- While traversing, maintain firstPrev to store previous node of fast pointer.
- Now, increment slow and fast pointers by a node in each iteration, until fast->next becomes equal to NULL.
- While traversing, maintain secondPrev to store previous node of slow pointer.
- Delete both the nodes of the Linked List, using firstPrev and secondPrev pointers.
- Print the updated linked list.
Below is the implementation of the above approach:
C++14
// C++ implementation of the above approach#include <bits/stdc++.h>#include <iostream>using namespace std;// Structure of a// Linked list Nodestruct Node { int data; struct Node* next;};// Function to insert a new node// at the front of the Linked Listvoid push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node;}// Function to print the Linked Listvoid printList(struct Node* node){ // while node is not NULL while (node != NULL) { cout << node->data << " "; node = node->next; } cout << endl;}// Function to delete nodes from// both ends of a Linked ListNode* DeleteNodesfromBothEnds(struct Node** head_ref, int k){ // Empty List if (head_ref == NULL) return *head_ref; // Represent nodes that remove // the next node of each Node* firstPrev = NULL; Node* secondPrev = NULL; Node* fast = *head_ref; // copy of head_ref Node* head = *head_ref; // Move fast to (k - 1) // nodes ahead of slow for (int i = 0; i < k - 1; ++i) { firstPrev = fast; fast = fast->next; } Node* slow = *head_ref; // Iterate until fast reaches // end of the Linked List while (fast != NULL && fast->next != NULL) { secondPrev = slow; slow = slow->next; fast = fast->next; } // Remove first node if (firstPrev == secondPrev) { if (firstPrev == NULL) { // Remove the head node head = head->next; } else { // Remove the middle Node firstPrev->next = firstPrev->next->next; } } else if (firstPrev != NULL && secondPrev != NULL && (firstPrev->next == secondPrev || secondPrev->next == firstPrev)) { // If firstPrev comes first if (firstPrev->next == secondPrev) firstPrev->next = secondPrev->next->next; // If secondPrev comes first else secondPrev->next = firstPrev->next->next; } else { // Remove the head node if (firstPrev == NULL) { head = head->next; } else { // Removethe first Node firstPrev->next = firstPrev->next->next; } // Remove the head node if (secondPrev == NULL) { head = head->next; } else { // Remove the second Node secondPrev->next = secondPrev->next->next; } } return head;}// Driver codeint main(){ // Given Linked List struct Node* head = NULL; push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); // Given position int K = 3; printList(head); // Function call to delete nodes // from both ends of Linked List head = DeleteNodesfromBothEnds(&head, K); // Print the updated Linked List printList(head); return 0;} |
Java
// Java implementation of the approachimport java.io.*;public class Simple { // Stores the head and tail // of the Linked List Node head = null; Node tail = null; // Structure of a // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Function to delete nodes from // both ends of a Linked List Node DeleteNodesfromBothEnds(int k) { // Empty List if (head == null) return head; // Represent nodes that remove // the next node of each Node firstPrev = null, secondPrev = null; Node fast = head; // Move fast to (k - 1) // nodes ahead of slow for (int i = 0; i < k - 1; ++i) { firstPrev = fast; fast = fast.next; } Node slow = head; // Iterate until fast reaches // end of the Linked List while (fast != null && fast.next != null) { secondPrev = slow; slow = slow.next; fast = fast.next; } // Remove first node if (firstPrev == secondPrev) { if (firstPrev == null) { // Remove the head node head = head.next; } else { // Remove the middle Node firstPrev.next = firstPrev.next.next; } } else if (firstPrev != null && secondPrev != null && (firstPrev.next == secondPrev || secondPrev.next == firstPrev)) { // If firstPrev comes first if (firstPrev.next == secondPrev) firstPrev.next = secondPrev.next.next; // If secondPrev comes first else secondPrev.next = firstPrev.next.next; } else { // Remove the head node if (firstPrev == null) { head = head.next; } else { // Removethe first Node firstPrev.next = firstPrev.next.next; } // Remove the head node if (secondPrev == null) { head = head.next; } else { // Remove the second Node secondPrev.next = secondPrev.next.next; } } return head; } // Function to insert a new node // at the end of the Linked List public void push(int new_data) { Node new_node = new Node(new_data); if (head == null) { head = new_node; tail = new_node; } else { tail.next = new_node; tail = new_node; } } // Function to print the Linked List public void printList() { Node tnode = head; // while tnode is not NULL while (tnode != null) { System.out.print(tnode.data + " "); tnode = tnode.next; } } // Driver Code public static void main(String[] args) { // Given Linked List Simple llist = new Simple(); llist.push(1); llist.push(2); llist.push(3); llist.push(4); llist.push(5); llist.push(6); // Given position int K = 3; // Function call to delete nodes // from both ends of Linked List llist.DeleteNodesfromBothEnds(K); // Print the updated Linked List llist.printList(); }} |
Python3
# Structure of a node in a Linked Listclass Node: def __init__(self): self.data = 0 self.next = None# Function to insert a new node at the front of the Linked Listdef push(head_ref, new_data): # Create a new node new_node = Node() # Assign data to the node new_node.data = new_data # Set the next pointer of the node to the current head of the Linked List new_node.next = head_ref # Set the head of the Linked List to the new node head_ref = new_node # Return the updated head of the Linked List return head_ref# Function to print the Linked Listdef print_list(node): # Iterate through the Linked List until we reach the end while node is not None: # Print the data of the current node print(node.data, end=' ') # Move on to the next node node = node.next # Print a new line at the end print()# Function to delete nodes from both ends of a Linked Listdef delete_nodes_from_both_ends(head_ref, k): # If the Linked List is empty, return the empty list if head_ref is None: return head_ref # Initialize variables to store the nodes that will remove the next node first_prev = None second_prev = None # Create a fast pointer that starts at the head of the Linked List fast = head_ref # Create a copy of the head of the Linked List head = head_ref # Move the fast pointer k - 1 nodes ahead of the slow pointer for i in range(k - 1): first_prev = fast fast = fast.next # Create a slow pointer that starts at the head of the Linked List slow = head_ref # Iterate until the fast pointer reaches the end of the Linked List while fast is not None and fast.next is not None: # Update the second_prev node to be the current slow pointer second_prev = slow # Move the slow pointer to the next node slow = slow.next # Move the fast pointer to the next node fast = fast.next # If first_prev and second_prev are the same, then we need to remove the node that follows first_prev if first_prev == second_prev: # If first_prev is None, then we are removing the head node if first_prev is None: head = head.next # If first_prev is not None, then we are removing a node in the middle of the Linked List else: first_prev.next = first_prev.next.next # If first_prev and second_prev are different and they are adjacent, then we need to remove the node between them elif first_prev is not None and second_prev is not None and (first_prev.next == second_prev or second_prev.next == first_prev): if first_prev.next == second_prev: first_prev.next = second_prev.next.next else: second_prev.next = first_prev.next.next else: if first_prev is None: head = head.next else: first_prev.next = first_prev.next.next if second_prev is None: head = head.next else: second_prev.next = second_prev.next.next return head# Driver Codehead = Nonehead = push(head, 6)head = push(head, 5)head = push(head, 4)head = push(head, 3)head = push(head, 2)head = push(head, 1)# Function callsk = 3print_list(head)head = delete_nodes_from_both_ends(head, k)print_list(head)# This code is contributed by phasing17. |
C#
// C# implementation of the approachusing System;public class Simple { // Stores the head and tail // of the Linked List public Node head = null; public Node tail = null; // Structure of a // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Function to delete nodes from // both ends of a Linked List public Node DeleteNodesfromBothEnds(int k) { // Empty List if (head == null) return head; // Represent nodes that remove // the next node of each Node firstPrev = null, secondPrev = null; Node fast = head; // Move fast to (k - 1) // nodes ahead of slow for (int i = 0; i < k - 1; ++i) { firstPrev = fast; fast = fast.next; } Node slow = head; // Iterate until fast reaches // end of the Linked List while (fast != null && fast.next != null) { secondPrev = slow; slow = slow.next; fast = fast.next; } // Remove first node if (firstPrev == secondPrev) { if (firstPrev == null) { // Remove the head node head = head.next; } else { // Remove the middle Node firstPrev.next = firstPrev.next.next; } } else if (firstPrev != null && secondPrev != null && (firstPrev.next == secondPrev || secondPrev.next == firstPrev)) { // If firstPrev comes first if (firstPrev.next == secondPrev) firstPrev.next = secondPrev.next.next; // If secondPrev comes first else secondPrev.next = firstPrev.next.next; } else { // Remove the head node if (firstPrev == null) { head = head.next; } else { // Removethe first Node firstPrev.next = firstPrev.next.next; } // Remove the head node if (secondPrev == null) { head = head.next; } else { // Remove the second Node secondPrev.next = secondPrev.next.next; } } return head; } // Function to insert a new node // at the end of the Linked List public void push(int new_data) { Node new_node = new Node(new_data); if (head == null) { head = new_node; tail = new_node; } else { tail.next = new_node; tail = new_node; } } // Function to print the Linked List public void printList() { Node tnode = head; // while tnode is not NULL while (tnode != null) { Console.Write(tnode.data + " "); tnode = tnode.next; } } // Driver Code public static void Main(String[] args) { // Given Linked List Simple llist = new Simple(); llist.push(1); llist.push(2); llist.push(3); llist.push(4); llist.push(5); llist.push(6); // Given position int K = 3; // Function call to delete nodes // from both ends of Linked List llist.DeleteNodesfromBothEnds(K); // Print the updated Linked List llist.printList(); }}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript implementation of the above approach// Structure of a// Linked list Nodeclass Node { constructor() { this.data = 0; this.next = null; }};// Function to insert a new node// at the front of the Linked Listfunction push(head_ref, new_data){ var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref;}// Function to print the Linked Listfunction printList(node){ // while node is not null while (node != null) { document.write( node.data + " "); node = node.next; } document.write("<br>");}// Function to delete nodes from// both ends of a Linked Listfunction DeleteNodesfromBothEnds(head_ref, k){ // Empty List if (head_ref == null) return head_ref; // Represent nodes that remove // the next node of each var firstPrev = null; var secondPrev = null; var fast = head_ref; // copy of head_ref var head = head_ref; // Move fast to (k - 1) // nodes ahead of slow for (var i = 0; i < k - 1; ++i) { firstPrev = fast; fast = fast.next; } var slow = head_ref; // Iterate until fast reaches // end of the Linked List while (fast != null && fast.next != null) { secondPrev = slow; slow = slow.next; fast = fast.next; } // Remove first node if (firstPrev == secondPrev) { if (firstPrev == null) { // Remove the head node head = head.next; } else { // Remove the middle Node firstPrev.next = firstPrev.next.next; } } else if (firstPrev != null && secondPrev != null && (firstPrev.next == secondPrev || secondPrev.next == firstPrev)) { // If firstPrev comes first if (firstPrev.next == secondPrev) firstPrev.next = secondPrev.next.next; // If secondPrev comes first else secondPrev.next = firstPrev.next.next; } else { // Remove the head node if (firstPrev == null) { head = head.next; } else { // Removethe first Node firstPrev.next = firstPrev.next.next; } // Remove the head node if (secondPrev == null) { head = head.next; } else { // Remove the second Node secondPrev.next = secondPrev.next.next; } } return head;}// Driver code// Given Linked Listvar head = null;head = push(head, 6);head = push(head, 5);head = push(head, 4);head = push(head, 3);head = push(head, 2);head = push(head, 1);// Given positionvar K = 3;printList(head);// Function call to delete nodes// from both ends of Linked Listhead = DeleteNodesfromBothEnds(head, K);// Print the updated Linked ListprintList(head);// This code is contributed by rrrtnx.</script> |
Output
1 2 3 4 5 6 1 2 5 6
Time Complexity: O(N)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
