Given a Singly Linked List, starting from the second node delete all alternate nodes of it. For example, if the given linked list is 1->2->3->4->5 then your function should convert it to 1->3->5, and if the given linked list is 1->2->3->4 then convert it to 1->3.
Method 1 (Iterative)
Keep track of previous of the node to be deleted. First, change the next link of the previous node and iteratively move to the next node.
C++
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
};
void deleteAlt(Node *head)
{
if (head == NULL)
return;
Node *prev = head;
Node *node = head->next;
while (prev != NULL && node != NULL)
{
prev->next = node->next;
delete(node);
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}
void push(Node** head_ref, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node *node)
{
while (node != NULL)
{
cout<< node->data<<" ";
node = node->next;
}
}
int main()
{
Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout<<"List before calling deleteAlt() \n";
printList(head);
deleteAlt(head);
cout<<"\nList after calling deleteAlt() \n";
printList(head);
return 0;
}
|
C
#include<stdio.h>
#include<stdlib.h>
struct Node
{
int data;
struct Node *next;
};
void deleteAlt(struct Node *head)
{
if (head == NULL)
return;
struct Node *prev = head;
struct Node *node = head->next;
while (prev != NULL && node != NULL)
{
prev->next = node->next;
free(node);
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}
void 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;
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
int main()
{
struct Node* head = NULL;
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("\nList before calling deleteAlt() \n");
printList(head);
deleteAlt(head);
printf("\nList after calling deleteAlt() \n");
printList(head);
return 0;
}
|
Java
class LinkedList {
Node head;
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void deleteAlt()
{
if (head == null)
return;
Node node = head;
while (node != null && node.next != null) {
node.next = node.next.next;
node = node.next;
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println(
"Linked List before calling deleteAlt() ");
llist.printList();
llist.deleteAlt();
System.out.println(
"Linked List after calling deleteAlt() ");
llist.printList();
}
}
|
Python3
import math
class Node:
def __init__(self, data):
self.data = data
self.next = None
def deleteAlt(head):
if (head == None):
return
prev = head
now = head.next
while (prev != None and now != None):
prev.next = now.next
now = None
prev = prev.next
if (prev != None):
now = prev.next
def push(head_ref, new_data):
new_node = Node(new_data)
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
def printList(node):
while (node != None):
print(node.data, end = " ")
node = node.next
if __name__=='__main__':
head = None
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("List before calling deleteAlt() ")
printList(head)
deleteAlt(head)
print("\nList after calling deleteAlt() ")
printList(head)
|
C#
using System;
public class LinkedList
{
Node head;
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
void deleteAlt()
{
if (head == null)
return;
Node prev = head;
Node now = head.next;
while (prev != null && now != null)
{
prev.next = now.next;
now = null;
prev = prev.next;
if (prev != null)
now = prev.next;
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
void printList()
{
Node temp = head;
while(temp != null)
{
Console.Write(temp.data+" ");
temp = temp.next;
}
Console.WriteLine();
}
public static void Main(String []args)
{
LinkedList llist = new LinkedList();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
Console.WriteLine("Linked List before" +
"calling deleteAlt() ");
llist.printList();
llist.deleteAlt();
Console.WriteLine("Linked List after" +
"calling deleteAlt() ");
llist.printList();
}
}
|
Javascript
<script>
var head;
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function deleteAlt() {
if (head == null)
return;
var prev = head;
var now = head.next;
while (prev != null && now != null) {
prev.next = now.next;
now = null;
prev = prev.next;
if (prev != null)
now = prev.next;
}
}
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
function printList() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
push(5);
push(4);
push(3);
push(2);
push(1);
document.write(
"Linked List before calling deleteAlt() <br/>"
);
printList();
deleteAlt();
document.write(
"Linked List after calling deleteAlt()<br/> "
);
printList();
</script>
|
Output
List before calling deleteAlt()
1 2 3 4 5
List after calling deleteAlt()
1 3 5
Time Complexity: O(n)
where n is the number of nodes in the given Linked List.
Auxiliary Space: O(1)
As constant extra space is used.
Method 2 (Recursive)
Recursive code uses the same approach as method 1. The recursive code is simple and short but causes O(n) recursive function calls for a linked list of size n.
C++
void deleteAlt(Node *head)
{
if (head == NULL)
return;
Node *node = head->next;
if (node == NULL)
return;
head->next = node->next;
free(node);
deleteAlt(head->next);
}
|
C
void deleteAlt(struct Node *head)
{
if (head == NULL)
return;
struct Node *node = head->next;
if (node == NULL)
return;
head->next = node->next;
free(node);
deleteAlt(head->next);
}
|
Java
static Node deleteAlt(Node head)
{
if (head == null)
return;
Node node = head.next;
if (node == null)
return;
head.next = node.next;
head.next = deleteAlt(head.next);
}
|
Python3
def deleteAlt(head):
if (head == None):
return
node = head.next
if (node == None):
return
head.next = node.next
deleteAlt(head.next)
|
C#
static Node deleteAlt(Node head)
{
if (head == null)
return;
Node node = head.next;
if (node == null)
return;
head.next = node.next;
head.next = deleteAlt(head.next);
}
|
Javascript
<script>
function deleteAlt(head)
{
if (head == null)
return;
var node = head.next;
if (node == null)
return;
head.next = node.next;
head.next = deleteAlt(head.next);
}
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
As this is a tail recursive function no function call stack is required thus the extra space used is constant.
Please write comments if you find the above code/algorithm incorrect, or find better ways to solve the same problem.
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 geeks!