# 如何交换链表中的节点而不交换数据？

2021年3月11日17:53:37 发表评论 364 次浏览

## 本文概述

``````Input:  10->15->12->13->20->14, x = 12, y = 20
Output: 10->15->20->13->12->14

Input:  10->15->12->13->20->14, x = 10, y = 20
Output: 20->15->12->13->10->14

Input:  10->15->12->13->20->14, x = 12, y = 13
Output: 10->15->13->12->20->14``````

{IDE}

1)x和y可以相邻也可以不相邻。

2)x或y都可以是头节点。

3)x或y可能是最后一个节点。

4)x和/或y可能不在链接列表中。

## C ++

``````/* This program swaps the nodes of linked list rather
than swapping the field from the nodes.*/
#include <bits/stdc++.h>
using namespace std;

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

/* Function to swap nodes x and y in linked list by
void swapNodes(Node **head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return ;

// Search for x (keep track of prevX and CurrX
Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x)
{
prevX = currX;
currX = currX->next;
}

// Search for y (keep track of prevY and CurrY
Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y)
{
prevY = currY;
currY = currY->next;
}

// If either x or y is not present, nothing to do
if (currX == NULL || currY == NULL)
return ;

if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head

if (prevY != NULL)
prevY->next = currX;
else // Else make x as new head

// Swap next pointers
Node *temp = currY->next;
currY->next = currX->next;
currX->next = temp;
}

/* Function to add a node at the beginning of 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 program to test above function */
int main()
{
Node *start = NULL;

/* The constructed linked list is:
1->2->3->4->5->6->7 */
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

cout << "Linked list before calling swapNodes() " ;
printList(start);

swapNodes(&start, 4, 3);

cout << "\nLinked list after calling swapNodes() " ;
printList(start);

return 0;
}

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

## C

``````/* This program swaps the nodes of linked list rather
than swapping the field from the nodes.*/

#include<stdio.h>
#include<stdlib.h>

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

/* Function to swap nodes x and y in linked list by
void swapNodes( struct Node **head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return ;

// Search for x (keep track of prevX and CurrX
struct Node *prevX = NULL, *currX = *head_ref;
while (currX && currX->data != x)
{
prevX = currX;
currX = currX->next;
}

// Search for y (keep track of prevY and CurrY
struct Node *prevY = NULL, *currY = *head_ref;
while (currY && currY->data != y)
{
prevY = currY;
currY = currY->next;
}

// If either x or y is not present, nothing to do
if (currX == NULL || currY == NULL)
return ;

if (prevX != NULL)
prevX->next = currY;
else // Else make y as new head

if (prevY != NULL)
prevY->next = currX;
else  // Else make x as new head

// Swap next pointers
struct Node *temp = currY->next;
currY->next = currX->next;
currX->next  = temp;
}

/* Function to add a node at the beginning of 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 function */
int main()
{
struct Node *start = NULL;

/* The constructed linked list is:
1->2->3->4->5->6->7 */
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

printf ( "\n Linked list before calling swapNodes() " );
printList(start);

swapNodes(&start, 4, 3);

printf ( "\n Linked list after calling swapNodes() " );
printList(start);

return 0;
}``````

## Java

``````// Java program to swap two given nodes of a linked list

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

{

/* Function to swap Nodes x and y in linked list by
public void swapNodes( int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return ;

// Search for x (keep track of prevX and CurrX)
Node prevX = null , currX = head;
while (currX != null && currX.data != x)
{
prevX = currX;
currX = currX.next;
}

// Search for y (keep track of prevY and currY)
Node prevY = null , currY = head;
while (currY != null && currY.data != y)
{
prevY = currY;
currY = currY.next;
}

// If either x or y is not present, nothing to do
if (currX == null || currY == null )
return ;

if (prevX != null )
prevX.next = currY;
else //make y the new head

if (prevY != null )
prevY.next = currX;
else // make x the new head

// Swap next pointers
Node temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}

/* Function to add Node at beginning of list. */
public void push( int new_data)
{
/* 1. alloc the Node and put the data */
Node new_Node = new Node(new_data);

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

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

/* This function prints contents of linked list starting
from the given Node */
public void printList()
{
while (tNode != null )
{
System.out.print(tNode.data+ " " );
tNode = tNode.next;
}
}

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

/* The constructed linked list is:
1->2->3->4->5->6->7 */
llist.push( 7 );
llist.push( 6 );
llist.push( 5 );
llist.push( 4 );
llist.push( 3 );
llist.push( 2 );
llist.push( 1 );

System.out.print( "\n Linked list before calling swapNodes() " );
llist.printList();

llist.swapNodes( 4 , 3 );

System.out.print( "\n Linked list after calling swapNodes() " );
llist.printList();
}
}
// This code is contributed by Rajat Mishra``````

## python

``````# Python program to swap two given nodes of a linked list
def __init__( self ):

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

# Function to swap Nodes x and y in linked list by
def swapNodes( self , x, y):

# Nothing to do if x and y are same
if x = = y:
return

# Search for x (keep track of prevX and CurrX)
prevX = None
while currX ! = None and currX.data ! = x:
prevX = currX
currX = currX. next

# Search for y (keep track of prevY and currY)
prevY = None
while currY ! = None and currY.data ! = y:
prevY = currY
currY = currY. next

# If either x or y is not present, nothing to do
if currX = = None or currY = = None :
return
if prevX ! = None :
prevX. next = currY
else : #make y the new head

if prevY ! = None :
prevY. next = currX
else : # make x the new head

# Swap next pointers
temp = currX. next
currX. next = currY. next
currY. next = temp

# Function to add Node at beginning of list.
def push( self , new_data):

# 1. alloc the Node and put the data
new_Node = self .Node(new_data)

# 2. Make next of new Node as head

# 3. Move the head to point to new Node

# This function prints contents of linked list starting
# from the given Node
def printList( self ):
while tNode ! = None :
print tNode.data, tNode = tNode. next

# Driver program to test above function

# The constructed linked list is:
# 1->2->3->4->5->6->7
llist.push( 7 )
llist.push( 6 )
llist.push( 5 )
llist.push( 4 )
llist.push( 3 )
llist.push( 2 )
llist.push( 1 )
print "Linked list before calling swapNodes() "
llist.printList()
llist.swapNodes( 4 , 3 )
print "\nLinked list after calling swapNodes() "
llist.printList()

# This code is contributed by BHAVYA JAIN``````

## C#

``````// C# program to swap two given
// nodes of a linked list
using System;

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

{

/* Function to swap Nodes x and y in
public void swapNodes( int x, int y)
{
// Nothing to do if x and y are same
if (x == y) return ;

// Search for x (keep track of prevX and CurrX)
Node prevX = null , currX = head;
while (currX != null && currX.data != x)
{
prevX = currX;
currX = currX.next;
}

// Search for y (keep track of prevY and currY)
Node prevY = null , currY = head;
while (currY != null && currY.data != y)
{
prevY = currY;
currY = currY.next;
}

// If either x or y is not present, nothing to do
if (currX == null || currY == null )
return ;

if (prevX != null )
prevX.next = currY;
else //make y the new head

if (prevY != null )
prevY.next = currX;
else // make x the new head

// Swap next pointers
Node temp = currX.next;
currX.next = currY.next;
currY.next = temp;
}

/* Function to add Node at beginning of list. */
public void push( int new_data)
{
/* 1. alloc the Node and put the data */
Node new_Node = new Node(new_data);

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

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

/* This function prints contents of linked list
starting from the given Node */
public void printList()
{
while (tNode != null )
{
Console.Write(tNode.data+ " " );
tNode = tNode.next;
}
}

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

/* The constructed linked list is:
1->2->3->4->5->6->7 */
llist.push(7);
llist.push(6);
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);

Console.Write( "\n Linked list before calling swapNodes() " );
llist.printList();

llist.swapNodes(4, 3);

Console.Write( "\n Linked list after calling swapNodes() " );
llist.printList();
}
}

// This code is contributed by 29AjayKumar``````

``````Linked list before calling swapNodes() 1 2 3 4 5 6 7
Linked list after calling swapNodes() 1 2 4 3 5 6 7``````

{IDE}

## C ++

``````// C++ program to swap two given nodes of a linked list
#include <iostream>

using namespace std;

// A linked list node class
class Node {

public :
int data;
class Node* next;

// constructor
Node( int val, Node* next)
: data(val), next(next)
{
}

// print list from this
// to last till null
void printList()
{

Node* node = this ;

while (node != NULL) {

cout << node->data;
node = node->next;
}

cout << endl;
}
};

// Function to add a node
// at the beginning of List
{

// allocate node
}

void swap(Node*& a, Node*& b)
{

Node* temp = a;
a = b;
b = temp;
}

void swapNodes(Node** head_ref, int x, int y)
{

// Nothing to do if x and y are same
if (x == y)
return ;

Node **a = NULL, **b = NULL;

// search for x and y in the linked list
// and store therir pointer in a and b

}

else if ((*head_ref)->data == y) {
}

}

// if we have found both a and b
// in the linked list swap current
// pointer and next pointer of these
if (a && b) {

swap(*a, *b);
swap(((*a)->next), ((*b)->next));
}
}

// Driver code
int main()
{

Node* start = NULL;

// The constructed linked list is:
// 1->2->3->4->5->6->7
push(&start, 7);
push(&start, 6);
push(&start, 5);
push(&start, 4);
push(&start, 3);
push(&start, 2);
push(&start, 1);

cout << "Linked list before calling swapNodes() " ;
start->printList();

swapNodes(&start, 6, 3);

cout << "Linked list after calling swapNodes() " ;
start->printList();
}``````

## Java

``````// Java program to swap two given nodes of a linked list
class Soluiton
{
// A linked list node class
static class Node {

int data;
Node next;

// constructor
Node( int val, Node next1)
{
data=val; next=next1;
}

// print list from this
// to last till null
void printList()
{

Node node = this ;

while (node != null ) {

System.out.print(node.data+ " " );
node = node.next;
}
System.out.println();
}
}

// Function to add a node
// at the beginning of List
static Node push(Node head_ref, int new_data)
{

// allocate node
}

static Node swapNodes(Node head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y)
return null ;

Node a = null , b = null ;

// search for x and y in the linked list
// and store therir pointer in a and b

}

else if ((head_ref.next).data == y) {
}

}

// if we have found both a and b
// in the linked list swap current
// pointer and next pointer of these
if (a!= null &&  b!= null ) {
Node temp = a.next;
a.next = b.next;
b.next = temp;
temp = a.next.next;
a.next.next = b.next.next;
b.next.next = temp;
}
}

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

Node start = null ;

// The constructed linked list is:
// 1.2.3.4.5.6.7
start=push(start, 7 );
start=push(start, 6 );
start=push(start, 5 );
start=push(start, 4 );
start=push(start, 3 );
start=push(start, 2 );
start=push(start, 1 );

System.out.print( "Linked list before calling swapNodes() " );
start.printList();

start=swapNodes(start, 6 , 3 );

System.out.print( "Linked list after calling swapNodes() " );
start.printList();
}
}
//contributed by Arnab Kundu``````

## Python3

``````# Python3 program to swap two given
# nodes of a linked list

# A linked list node class
class Node :

# constructor
def __init__( self , val = None , next1 = None ):
self .data = val
self . next = next1

# print list from this
# to last till None
def printList( self ):

node = self

while (node ! = None ) :
print (node.data, end = " " )
node = node. next
print ( " " )

# Function to add a node
# at the beginning of List

# allocate node

# Nothing to do if x and y are same
if (x = = y) :
return None

a = None
b = None

# search for x and y in the linked list
# and store therir pointer in a and b
while (head_ref. next ! = None ) :

if ((head_ref. next ).data = = x) :

elif ((head_ref. next ).data = = y) :

# if we have found both a and b
# in the linked list swap current
# pointer and next pointer of these
if (a ! = None and b ! = None ) :
temp = a. next
a. next = b. next
b. next = temp
temp = a. next . next
a. next . next = b. next . next
b. next . next = temp

# Driver code

start = None

# The constructed linked list is:
# 1.2.3.4.5.6.7
start = push(start, 7 )
start = push(start, 6 )
start = push(start, 5 )
start = push(start, 4 )
start = push(start, 3 )
start = push(start, 2 )
start = push(start, 1 )

print ( "Linked list before calling swapNodes() " )
start.printList()

start = swapNodes(start, 6 , 3 )

print ( "Linked list after calling swapNodes() " )
start.printList()

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

## C#

``````// C# program to swap two
// given nodes of a linked list
using System;

class GFG
{
// A linked list node class
public class Node
{

public int data;
public Node next;

// constructor
public Node( int val, Node next1)
{
data = val; next = next1;
}

// print list from this
// to last till null
public void printList()
{

Node node = this ;

while (node != null )
{
Console.Write(node.data+ " " );
node = node.next;
}
Console.WriteLine();
}
}

// Function to add a node
// at the beginning of List
static Node push(Node head_ref, int new_data)
{

// allocate node
}

static Node swapNodes(Node head_ref, int x, int y)
{

// Nothing to do if x and y are same
if (x == y)
return null ;

Node a = null , b = null ;

// search for x and y in the linked list
// and store therir pointer in a and b
{

{
}

{
}

}

// if we have found both a and b
// in the linked list swap current
// pointer and next pointer of these
if (a != null && b != null )
{
Node temp = a.next;
a.next = b.next;
b.next = temp;
temp = a.next.next;
a.next.next = b.next.next;
b.next.next = temp;
}
}

// Driver code
public static void Main()
{

Node start = null ;

// The constructed linked list is:
// 1.2.3.4.5.6.7
start=push(start, 7);
start=push(start, 6);
start=push(start, 5);
start=push(start, 4);
start=push(start, 3);
start=push(start, 2);
start=push(start, 1);

Console.Write( "Linked list before calling swapNodes() " );
start.printList();

start=swapNodes(start, 6, 3);

Console.Write( "Linked list after calling swapNodes() " );
start.printList();
}
}

/* This code contributed by PrinciRaj1992 */``````

``````Linked list before calling swapNodes() 1 2 3 4 5 6 7
Linked list after calling swapNodes() 1 2 6 4 5 3 7``````

。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。 