本文概述

• C ++
• C
• Java
• python
• C#
• C ++
• Java
• Python3
• C#

给定一个链表和其中的两个键, 将节点交换为两个给定的键。应通过更改链接来交换节点。当数据包含许多字段时, 在许多情况下交换节点的数据可能会很昂贵。
可以假定链接列表中的所有键都是不同的。
【如何交换链表中的节点而不交换数据（）】例子：

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

推荐：请尝试以下方法
{IDE}
首先, 在继续解决方案之前。
这可能看起来很简单, 但是却是一个有趣的问题, 因为有以下几种情况需要处理。
1)x和y可以相邻也可以不相邻。
2)x或y都可以是头节点。
3)x或y可能是最后一个节点。
4)x和/或y可能不在链接列表中。
如何编写干净的工作代码来处理上述所有可能性。
强烈建议最小化你的浏览器, 然后自己尝试。
这个想法是首先在给定的链表中搜索x和y。如果其中不存在, 则返回。在搜索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 changing links */ 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 x is not head of linked list if (prevX != NULL) prevX-> next = currY; else // Else make y as new head *head_ref = currY; // If y is not head of linked list if (prevY != NULL) prevY-> next = currX; else // Else make x as new head *head_ref = currX; // Swap next pointers Node *temp = currY-> next; currY-> next = currX-> next; currX-> next = temp; } /* Function to add a node at the beginning of List */ void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node-> data = https://www.lsbin.com/new_data; /* link the old list off the new node */ new_node-> next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = 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 changing links */ 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 x is not head of linked list if (prevX != NULL) prevX-> next = currY; else // Else make y as new head *head_ref = currY; // If y is not head of linked list if (prevY != NULL) prevY-> next = currX; else// Else make x as new head *head_ref = currX; // 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= https://www.lsbin.com/new_data; /* link the old list off the new node */ new_node-> next = (*head_ref); /* move the head to point to the new node */ (*head_ref)= 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 listclass Node { int data; Node next; Node( int d) { data = https://www.lsbin.com/d; next = null ; } }class LinkedList { Node head; // head of list/* Function to swap Nodes x and y in linked list by changing links */ 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 x is not head of linked list if (prevX != null ) prevX.next = currY; else //make y the new head head = currY; // If y is not head of linked list if (prevY != null ) prevY.next = currX; else // make x the new head head = currX; // 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 */ new_Node.next = head; /* 3. Move the head to point to new Node */ head = new_Node; }/* This function prints contents of linked list starting from the given Node */ public void printList() { Node tNode = head; while (tNode != null ) { System.out.print(tNode.data+" " ); tNode = tNode.next; } }/* Driver program to test above function */ public static void main(String[] args) { LinkedList llist = new LinkedList(); /* 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 class LinkedList( object ): def __init__( self ): self .head = None# head of list class Node( object ): def __init__( self , d): self .data = https://www.lsbin.com/d self . next = None# Function to swap Nodes x and y in linked list by # changing links 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 currX = self .head while currX ! = None and currX.data ! = x: prevX = currX currX = currX. next# Search for y (keep track of prevY and currY) prevY = None currY = self .head 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 x is not head of linked list if prevX ! = None : prevX. next = currY else : #make y the new head self .head = currY# If y is not head of linked list if prevY ! = None : prevY. next = currX else : # make x the new head self .head = currX# 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 new_Node. next = self .head# 3. Move the head to point to new Node self .head = new_Node# This function prints contents of linked list starting # from the given Node def printList( self ): tNode = self .head while tNode ! = None : print tNode.data, tNode = tNode. next# Driver program to test above function llist = LinkedList()# 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 = https://www.lsbin.com/d; next = null ; } } public class LinkedList { Node head; // head of list /* Function to swap Nodes x and y in linked list by changing links */ 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 x is not head of linked list if (prevX != null ) prevX.next = currY; else //make y the new head head = currY; // If y is not head of linked list if (prevY != null ) prevY.next = currX; else // make x the new head head = currX; // 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 */ new_Node.next = head; /* 3. Move the head to point to new Node */ head = new_Node; } /* This function prints contents of linked list starting from the given Node */ public void printList() { Node tNode = head; while (tNode != null ) { Console.Write(tNode.data+" " ); tNode = tNode.next; } } /* Driver code */ public static void Main(String[] args) { LinkedList llist = new LinkedList(); /* 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

优化：
可以优化以上代码以单遍搜索x和y。两个循环用于使程序保持简单。
更简单的方法–
推荐：请尝试以下方法
{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 void push(Node** head_ref, int new_data) {// allocate node (*head_ref) = new Node(new_data, *head_ref); }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 while (*head_ref) {if ((*head_ref)-> data =https://www.lsbin.com/= x) { a = head_ref; }else if ((*head_ref)-> data == y) { b = head_ref; }head_ref = & ((*head_ref)-> next); }// 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=https://www.lsbin.com/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 (head_ref) = new Node(new_data, head_ref); return head_ref; } static Node swapNodes(Node head_ref, int x, int y) { Node head=head_ref; // 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 while (head_ref.next!= null ) { if ((head_ref.next).data =https://www.lsbin.com/= x) { a = head_ref; } else if ((head_ref.next).data == y) { b = head_ref; } head_ref = ((head_ref).next); } // 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; } return head; } //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 = https://www.lsbin.com/val self . next = next1# print list from this # to last till None def printList( self ): node = selfwhile (node ! = None ) : print (node.data, end =" " ) node = node. next print ( " " )# Function to add a node # at the beginning of List def push(head_ref, new_data) :# allocate node (head_ref) = Node(new_data, head_ref) return head_refdef swapNodes(head_ref, x, y) : head = head_ref# Nothing to do if x and y are same if (x = = y) : return Nonea = 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 = https://www.lsbin.com/= x) : a = head_ref elif ((head_ref. next ).data = = y) : b = head_ref head_ref = ((head_ref). next ) # 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 return head# Driver codestart = 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 = https://www.lsbin.com/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 (head_ref) = new Node(new_data, head_ref); return head_ref; } static Node swapNodes(Node head_ref, int x, int y) { Node head=head_ref; // 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 while (head_ref.next!= null ) { if ((head_ref.next).data =https://www.lsbin.com/= x) { a = head_ref; } else if ((head_ref.next).data == y) { b = head_ref; } head_ref = ((head_ref).next); } // 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; } return head; } // 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

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

推荐阅读

• 

  幻想全明星新英雄雏鹤爱图文介绍 幻想全明星雏鹤爱强不强 基本介绍
• 

  决战平安京袭色大噬魔丸怎么样 袭色大噬魔丸装备分析
• 

  女人也会长胡子？ 女生有胡子
• 

  如何去除衣服霉斑 衣服去除霉斑的教程
• 

  数据库解密工具，有个db数据文件能用Access能打开但是有密码有什么好密码破
• 

  UOS|统信UOS助手发布：支持“一键秒传”
• 

  板栗在冰箱保存方法 教你如何保鲜板栗
• 

  电脑怎么重装系统
• 

  go语言书适合初学者的书，go语言入门书籍
• 

  失策
• 

  4个月的宝宝感冒咳嗽、打喷嚏、流鼻涕能吃艾畅吗?
• 

  新鲜荔枝怎么保存
• 

  早上做平板支撑有什么好处
• 

  相机水下拍摄要用什么，水下拍摄的相机哪个牌子的好?
• 

  沈岸初夏是什么电视剧 沈岸初夏是什么电视剧最后一集
• 

  消化管共同具有的运动形式是
• 

  七星瓢虫和花大姐的区别
• 

  前轮前束正常值是多少
• 

  哪个网是正规的起名网 如何制作起名网站，网店名字大全 起名网
• 

  鲜枣有什么功效 新鲜大枣的好处

• 位与量子位之间的差异
• PHP |日历功能完整参考
• 组合博弈论 4（Sprague – Grundy定理）
• JavaScript Math log()方法介绍
• 算法设计（金矿问题解析和代码实现）
• 算法设计（扔鸡蛋问题 – 动态规划）
• Python MongoDB –查找数据用法介绍
• jQuery :最后一个子元素选择器用法介绍
• 人工智能|全连接层的算力计算方式