# 算法题：如何删除链表中的备用节点？详细实现

2021年3月24日13:52:38 发表评论 677 次浏览

## C ++

``````// C++ program to remove alternate
// nodes of a linked list
#include <bits/stdc++.h>
using namespace std;

/* A linked list node */
class Node
{
public :
int data;
Node *next;
};

/* deletes alternate nodes
of a list starting with head */
{
return ;

/* Initialize prev and node to be deleted */

while (prev != NULL && node != NULL)
{
/* Change next link of previous node */
prev->next = node->next;

/* Free memory */
free (node);

/* Update prev and node */
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
{
/* allocate node */
Node* new_node = new Node();

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print nodes in a given linked list */
void printList(Node *node)
{
while (node != NULL)
{
cout<< node->data<< " " ;
node = node->next;
}
}

/* Driver code */
int main()
{

/* Using push() to construct below list
1->2->3->4->5 */

cout<< "List before calling deleteAlt() \n" ;

cout<< "\nList after calling deleteAlt() \n" ;

return 0;
}

// This code is contributed by rathbhupendra``````

## C

``````// C program to remove alternate nodes of a linked list
#include<stdio.h>
#include<stdlib.h>

/* A linked list node */
struct Node
{
int data;
struct Node *next;
};

/* deletes alternate nodes of a list starting with head */
{
return ;

/* Initialize prev and node to be deleted */

while (prev != NULL && node != NULL)
{
/* Change next link of previous node */
prev->next = node->next;

/* Free memory */
free (node);

/* Update prev and node */
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}

/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push( struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
( struct Node*) malloc ( sizeof ( struct Node));

/* put in the data  */
new_node->data  = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print nodes in a given linked list */
void printList( struct Node *node)
{
while (node != NULL)
{
printf ( "%d " , node->data);
node = node->next;
}
}

/* Driver program to test above functions */
int main()
{

/* Using push() to construct below list
1->2->3->4->5  */

printf ( "\nList before calling deleteAlt() \n" );

printf ( "\nList after calling deleteAlt() \n" );

return 0;
}``````

## Java

``````// Java program to delete alternate nodes of a linked list
{

class Node
{
int data;
Node next;
Node( int d) {data = d; next = null ; }
}

void deleteAlt()
{
return ;

while (prev != null && now != null )
{
/* Change next link of previus node */
prev.next = now.next;

/* Free node */
now = null ;

/*Update prev and now */
prev = prev.next;
if (prev != null )
now = prev.next;
}
}

/* Utility functions */

/* Inserts a new Node at front of the list. */
public void push( int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

/* Function to print linked list */
void printList()
{
while (temp != null )
{
System.out.print(temp.data+ " " );
temp = temp.next;
}
System.out.println();
}

/* Driver program to test above functions */
public static void main(String args[])
{

/* Constructed Linked List is 1->2->3->4->5->null */
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();
}
}
/* This code is contributed by Rajat Mishra */``````

## Python3

``````# Python3 program to remove alternate
# nodes of a linked list
import math

class Node:
def __init__( self , data):
self .data = data
self . next = None

# deletes alternate nodes
# of a list starting with head
if (head = = None ):
return

# Initialize prev and node to be deleted

while (prev ! = None and now ! = None ):

# Change next link of previous node
prev. next = now. next

# Free memory
now = None

# Update prev and node
prev = prev. next
if (prev ! = None ):
now = prev. next

# UTILITY FUNCTIONS TO TEST fun1() and fun2()
# Given a reference (poer to poer) to the head
# of a list and an , push a new node on the front
# of the list.

# allocate node
new_node = Node(new_data)

# put in the data
new_node.data = new_data

# link the old list off the new node

# move the head to po to the new node

# Function to print nodes in a given linked list
def prList(node):
while (node ! = None ):
print (node.data, end = " " )
node = node. next

# Driver code
if __name__ = = '__main__' :

# Using head=push() to construct below list
# 1.2.3.4.5

print ( "List before calling deleteAlt() " )

print ( "\nList after calling deleteAlt() " )

# This code is contributed by Srathore``````

## C#

``````// C# program to delete alternate
// nodes of a linked list
using System;

{

public class Node
{
public int data;
public Node next;
public Node( int d)
{
data = d; next = null ;

}
}

void deleteAlt()
{
return ;

while (prev != null && now != null )
{
/* Change next link of previus node */
prev.next = now.next;

/* Free node */
now = null ;

/*Update prev and now */
prev = prev.next;
if (prev != null )
now = prev.next;
}
}

/* Utility functions */

/* Inserts a new Node at front of the list. */
public void push( int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

/* Function to print linked list */
void printList()
{
while (temp != null )
{
Console.Write(temp.data+ " " );
temp = temp.next;
}
Console.WriteLine();
}

/* Driver code*/
public static void Main(String []args)
{

1->2->3->4->5->null */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

"calling deleteAlt() " );
llist.printList();

llist.deleteAlt();

"calling deleteAlt() " );
llist.printList();
}
}

// This code has been contributed
// by 29AjayKumar``````

``````List before calling deleteAlt()
1 2 3 4 5
List after calling deleteAlt()
1 3 5``````

## C ++

``````/* deletes alternate nodes of a list starting with head */
{
return ;

if (node == NULL)
return ;

/* free memory allocated for node */
free (node);

/* Recursively call for the new next of head */
}

// This code is contributed by rathbhupendra``````

## C

``````/* deletes alternate nodes of a list starting with head */
{
return ;

if (node == NULL)
return ;

/* free memory allocated for node */
free (node);

/* Recursively call for the new next of head */
}``````

## Java

``````/* deletes alternate nodes of a list
{
return ;

if (node == null )
return ;

/* Recursively call for the new next of head */
}

// This code is contributed by Arnab Kundu``````

## Python3

``````# deletes alternate nodes of a list starting with head
if (head = = None ):
return

if (node = = None ):
return

# free memory allocated for node
#free(node)

# Recursively call for the new next of head

# This code is contributed by Srathore``````

## C#

``````/* deletes alternate nodes of a list
{
return ;

if (node == null )
return ;