给定一个链表和其中的两个键，为两个给定键交换节点。应该通过更改链接来交换节点。在数据包含多个字段的许多情况下，交换节点的数据可能代价高昂。
null
可以假设链表中的所有键都是不同的。
例如：
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
这看起来可能是一个简单的问题，但这是一个有趣的问题，因为它需要处理以下情况。
- x和y可能相邻，也可能不相邻。
- x或y可以是头部节点。
- x或y可能是最后一个节点。
- 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 = 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 << "Linked 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 = 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 ( " Linked list before calling swapNodes() " ); printList(start); swapNodes(&start, 4, 3); printf ( " 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 ; } } 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( " Linked list before calling swapNodes() " ); llist.printList(); llist.swapNodes( 4 , 3 ); System.out.print( " 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 = 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 "Linked 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 ; } } 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( " Linked list before calling swapNodes() " ); llist.printList(); llist.swapNodes(4, 3); Console.Write( " Linked list after calling swapNodes() " ); llist.printList(); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program to swap two // given nodes of a linked list class Node { constructor(val) { this .data = val; this .next = null ; } } var head; // head of list /* Function to swap Nodes x and y in linked list by changing links */ function swapNodes(x , y) { // Nothing to do if x and y are same if (x == y) return ; // Search for x (keep track of prevX and CurrX) var prevX = null , currX = head; while (currX != null && currX.data != x) { prevX = currX; currX = currX.next; } // Search for y (keep track of prevY and currY) var 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 var temp = currX.next; currX.next = currY.next; currY.next = temp; } /* Function to add Node at beginning of list. */ function push(new_data) { /* 1. alloc the Node and put the data */ var 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 */ function printList() { var tNode = head; while (tNode != null ) { document.write(tNode.data + " " ); tNode = tNode.next; } } /* Driver program to test above function */ /* The constructed linked list is: 1->2->3->4->5->6->7 */ push(7); push(6); push(5); push(4); push(3); push(2); push(1); document.write( " Linked list before calling swapNodes()<br/> " ) ; printList(); swapNodes(4, 3); document.write( "<br/> Linked list after calling swapNodes() <br/>" ); printList(); // This code is contributed by todaysgaurav </script> |
输出
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。两个循环用于保持程序简单。
更简单的方法——
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 their pointer in a and b while (*head_ref) { if ((*head_ref)->data == 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, 1); cout << "Linked list after calling swapNodes() " ; start->printList(); } |
JAVA
// Java program to swap two given nodes of a linked list public class Solution { // Represent a node of the singly linked list class Node { int data; Node next; public Node( int data) { this .data = data; this .next = null ; } } // Represent the head and tail of the singly linked list public Node head = null ; public Node tail = null ; // addNode() will add a new node to the list public void addNode( int data) { // Create a new node Node newNode = new Node(data); // Checks if the list is empty if (head == null ) { // If list is empty, both head and // tail will point to new node head = newNode; tail = newNode; } else { // newNode will be added after tail such that // tail's next will point to newNode tail.next = newNode; // newNode will become new tail of the list tail = newNode; } } // swap() will swap the given two nodes public void swap( int n1, int n2) { Node prevNode1 = null , prevNode2 = null , node1 = head, node2 = head; // Checks if list is empty if (head == null ) { return ; } // If n1 and n2 are equal, then // list will remain the same if (n1 == n2) return ; // Search for node1 while (node1 != null && node1.data != n1) { prevNode1 = node1; node1 = node1.next; } // Search for node2 while (node2 != null && node2.data != n2) { prevNode2 = node2; node2 = node2.next; } if (node1 != null && node2 != null ) { // If previous node to node1 is not null then, // it will point to node2 if (prevNode1 != null ) prevNode1.next = node2; else head = node2; // If previous node to node2 is not null then, // it will point to node1 if (prevNode2 != null ) prevNode2.next = node1; else head = node1; // Swaps the next nodes of node1 and node2 Node temp = node1.next; node1.next = node2.next; node2.next = temp; } else { System.out.println( "Swapping is not possible" ); } } // display() will display all the // nodes present in the list public void display() { // Node current will point to head Node current = head; if (head == null ) { System.out.println( "List is empty" ); return ; } while (current != null ) { // Prints each node by incrementing pointer System.out.print(current.data + " " ); current = current.next; } System.out.println(); } public static void main(String[] args) { Solution sList = new Solution(); // Add nodes to the list sList.addNode( 1 ); sList.addNode( 2 ); sList.addNode( 3 ); sList.addNode( 4 ); sList.addNode( 5 ); sList.addNode( 6 ); sList.addNode( 7 ); System.out.println( "Original list: " ); sList.display(); // Swaps the node 2 with node 5 sList.swap( 6 , 1 ); System.out.println( "List after swapping nodes: " ); sList.display(); } } |
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 def push(head_ref, new_data): # allocate node (head_ref) = Node(new_data, head_ref) return head_ref def swapNodes(head_ref, x, y): head = head_ref # 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 their pointer in a and b while (head_ref. next ! = None ): if ((head_ref. next ).data = = 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 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 , 1 ) 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 (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 their pointer in a and b while (head_ref.next != null ) { if ((head_ref.next).data == 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, 1); Console.Write( "Linked list after calling swapNodes() " ); start.printList(); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // javascript program to swap two given nodes of a linked list // Represent a node of the singly linked list class Node { constructor(val) { this .data = val; this .next = null ; } } // Represent the head and tail of the singly linked list var head = null ; var tail = null ; // addNode() will add a new node to the list function addNode(data) { // Create a new node var newNode = new Node(data); // Checks if the list is empty if (head == null ) { // If list is empty, both head and // tail will point to new node head = newNode; tail = newNode; } else { // newNode will be added after tail such that // tail's next will point to newNode tail.next = newNode; // newNode will become new tail of the list tail = newNode; } } // swap() will swap the given two nodes function swap(n1 , n2) { var prevNode1 = null , prevNode2 = null , node1 = head, node2 = head; // Checks if list is empty if (head == null ) { return ; } // If n1 and n2 are equal, then // list will remain the same if (n1 == n2) return ; // Search for node1 while (node1 != null && node1.data != n1) { prevNode1 = node1; node1 = node1.next; } // Search for node2 while (node2 != null && node2.data != n2) { prevNode2 = node2; node2 = node2.next; } if (node1 != null && node2 != null ) { // If previous node to node1 is not null then, // it will point to node2 if (prevNode1 != null ) prevNode1.next = node2; else head = node2; // If previous node to node2 is not null then, // it will point to node1 if (prevNode2 != null ) prevNode2.next = node1; else head = node1; // Swaps the next nodes of node1 and node2 var temp = node1.next; node1.next = node2.next; node2.next = temp; } else { document.write( "Swapping is not possible" ); } } // display() will display all the // nodes present in the list function display() { // Node current will point to head var current = head; if (head == null ) { document.write( "List is empty" ); return ; } while (current != null ) { // Prints each node by incrementing pointer document.write(current.data + " " ); current = current.next; } document.write(); } // Add nodes to the list addNode(1); addNode(2); addNode(3); addNode(4); addNode(5); addNode(6); addNode(7); document.write( "Original list:<br/> " ); display(); // Swaps the node 2 with node 5 swap(6, 1); document.write( "<br/>List after swapping nodes: <br/>" ); display(); // This code contributed by aashish1995 </script> |
输出
Linked list before calling swapNodes() 1 2 3 4 5 6 7 Linked list after calling swapNodes() 6 2 3 4 5 1 7
https://www.youtube.com/watch?v=V4ZHvhvVmSE
本文由 高塔姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
