{"id":3836,"date":"2021-08-12T09:56:49","date_gmt":"2021-08-12T09:56:49","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3836"},"modified":"2022-11-22T07:21:48","modified_gmt":"2022-11-22T07:21:48","slug":"delete-alternate-nodes-of-a-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/delete-alternate-nodes-of-a-linked-list\/","title":{"rendered":"Delete Alternate Nodes Of A Linked List"},"content":{"rendered":"

\"\"<\/p>\n

We have seen various approaches and various types of deletion in linked lists such as Deleting a linked list, deleting the first node of linked list, deleting the last node of linked list, deleting the middle node of linked list and deleting the smaller and larger nodes of linked list. Now in the below article we will see how to delete alternate nodes of a linked list.<\/p>\n

How to Delete Alternate Nodes of a Linked List.<\/h2>\n

Given a singly linked list. Remove its alternate nodes.<\/p>\n

Example<\/strong><\/p>\n

Sample Input: 3->5->2->6->8\nSample Output: 3->2->8\n\nHere 5 and 6 were the nodes at alternate positions. So, we have removed them.\n\nSample Input: 3->5->2->6->8->7\nSample Output: 3->2->8\n\nHere 5, 6, and 7 were nodes at alternate positions. So, we have removed them.<\/code><\/pre>\n
In this problem, we have to delete alternate nodes of the given linked list. Deleting alternate nodes means deleting nodes at alternate positions in the linked list.<\/p>\n
Let\u2019s understand this:
\nConsider a linked list 3->5->2->6->8->7 and lets mark the positions of the node (Using 1 based indexing).<\/p>\n
\"\"<\/p>\n
If we start from position 1, the alternate nodes are at positions 2, 4, and 6.<\/p>\n
Can you observe something about the alternate positions?
\nNow, hopefully i think it is clear what we have to do in this problem.<\/p>\n
Approach (Iterative)  of how to delete alternate nodes of a linked list<\/h2>\n
I hope you have understood the problem and have got a basic idea of what we are going to do.<\/p>\n
We can observe from the above example that the alternate positions are the positions that are even. So, deleting alternate nodes becomes deleting nodes at even positions in the linked list. To do so, the idea is simple, while iterating through the linked list we need to keep a track of the node\u2019s position and a pointer to the previous node. After reaching an even position, we just need to remove that node from the linked list and move ahead.<\/p>\n
Since it is clear what we need to do, take some time and think about how we are going to do it. Below is the algorithm explaining the steps we need to take to implement our idea.<\/p>\n
Algorithm  of how to delete alternate nodes of a linked list<\/h2>\n
    \n
  • Declare three variables: \u2018curr\u2019, \u2018position\u2019 and \u2018prev\u2019.<\/li>\n
  • Initialize position as 1 and prev as \u2018NULL\u2019 and \u2018curr\u2019 to head.<\/li>\n
  • Iterate through the linked list using curr and update positions and prev.<\/li>\n
  • If we reach an even position, delete the node at that position from the linked list by connecting the previous node to the next node of curr and deleting the current node, and move ahead.<\/li>\n<\/ul>\n
    Dry Run  of how to delete alternate nodes of a linked list<\/h3>\n
    \"\"<\/p>\n
    Code Implementation  of how to delete alternate nodes of a linked list<\/h2>\n\t\t\t\t\t\t