Given a singly linked list, Your task is to remove every K-th node of the linked list. Assume that K is always less than or equal to length of Linked List.
Examples :
Input: 1->2->3->4->5->6->7->8
k = 3
Output: 1->2->4->5->7->8
As 3 is the k-th node after its deletion list
would be 1->2->4->5->6->7->8
And now 4 is the starting node then from it, 6
would be the k-th node. So no other kth node
could be there.So, final list is:
1->2->4->5->7->8.
Input: 1->2->3->4->5->6
k = 1
Output: Empty list
All nodes need to be deleted
The idea is to traverse the list from the beginning and keep track of nodes visited after the last deletion. Whenever count becomes k, delete the current node and reset the count as 0.
Traverse list and do following
(a) Count node before deletion.
(b) If (count == k) that means current
node is to be deleted.
(i) Delete current node i.e. do
// assign address of next node of
// current node to the previous node
// of the current node.
prev->next = ptr->next i.e.
(ii) Reset count as 0, i.e., do count = 0.
(c) Update prev node if count != 0 and if
count is 0 that means that node is a
starting point.
(d) Update ptr and continue until all
k-th node gets deleted.
Below is the implementation.
Java
// Java program to delete every k-th // Node of a singly linked list. class GFG{ // Linked list Node static class Node { int data; Node next; } // To remove complete list (Needed // for case when k is 1) static Node freeList(Node node) { while (node != null) { Node next = node.next; node = next; } return node; } // Deletes every k-th node and // returns head of modified list. static Node deleteKthNode(Node head, int k) { // If linked list is empty if (head == null) return null; if (k == 1) { head = freeList(head); return null; } // Initialize ptr and prev before // starting traversal. Node ptr = head, prev = null; // Traverse list and delete // every k-th node int count = 0; while (ptr != null) { // Increment Node count count++; // Check if count is equal to k // if yes, then delete current Node if (k == count) { // Put the next of current Node in // the next of previous Node prev.next = ptr.next; // Set count = 0 to reach further // k-th Node count = 0; } // Update prev if count is not 0 if (count != 0) prev = ptr; ptr = prev.next; } return head; } // Function to print linked list static void displayList(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } } // Utility function to create a // new node. static Node newNode(int x) { Node temp = new Node(); temp.data = x; temp.next = null; return temp; } // Driver Code public static void main(String args[]) { // Start with the empty list Node head = newNode(1); head.next = newNode(2); head.next.next = newNode(3); head.next.next.next = newNode(4); head.next.next.next.next = newNode(5); head.next.next.next.next.next = newNode(6); head.next.next.next.next.next.next = newNode(7); head.next.next.next.next.next.next.next = newNode(8); int k = 3; head = deleteKthNode(head, k); displayList(head); } } // This code is contributed by Arnab Kundu |
Output:
1 2 4 5 7 8
Time Complexity: O(n)
Please refer complete article on Remove every k-th node of the linked list for more details!
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!
Share your thoughts in the comments
