给定一个单链表，从开始交换第k个节点，从结束交换第k个节点。 不允许交换数据，只应更改指针。 在链表数据部分很大的许多情况下（例如学生详细信息行名称、RollNo、地址等），这个要求可能是合乎逻辑的。指针总是固定的（大多数编译器为4字节）。 例子：
null
Input: 1 -> 2 -> 3 -> 4 -> 5, K = 2Output: 1 -> 4 -> 3 -> 2 -> 5 Explanation: The 2nd node from 1st is 2 and 2nd node from last is 4, so swap them.Input: 1 -> 2 -> 3 -> 4 -> 5, K = 5Output: 5 -> 2 -> 3 -> 4 -> 1 Explanation: The 5th node from 1st is 5 and 5th node from last is 1, so swap them.
插图：
![图片[1]-在链表中，从开始处将第k个节点替换为从结束处的第k个节点-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200715023818/Untitled-Diagram-205.png)
方法： 这个想法非常简单，从一开始就找到第k个节点，最后一个节点的第k个节点是从一开始的n-k+1个节点。交换两个节点。 然而，也有一些角落案件必须处理
- Y紧挨着X
- X紧挨着Y
- X和Y是一样的
- X和Y不存在（k大于链表中的节点数）
以下是上述方法的实施情况。
C++
// A C++ program to swap Kth node // from beginning with kth node from end #include <bits/stdc++.h> using namespace std; // A Linked List node struct Node { int data; struct Node* next; }; /* Utility function to insert a node at the beginning */ 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; } /* Utility function for displaying linked list */ void printList( struct Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } cout << endl; } /* Utility function for calculating length of linked list */ int countNodes( struct Node* s) { int count = 0; while (s != NULL) { count++; s = s->next; } return count; } /* Function for swapping kth nodes from both ends of linked list */ void swapKth( struct Node** head_ref, int k) { // Count nodes in linked list int n = countNodes(*head_ref); // Check if k is valid if (n < k) return ; // If x (kth node from start) and // y(kth node from end) are same if (2 * k - 1 == n) return ; // Find the kth node from the beginning of // the linked list. We also find // previous of kth node because we // need to update next pointer of // the previous. Node* x = *head_ref; Node* x_prev = NULL; for ( int i = 1; i < k; i++) { x_prev = x; x = x->next; } // Similarly, find the kth node from // end and its previous. kth node // from end is (n-k+1)th node from beginning Node* y = *head_ref; Node* y_prev = NULL; for ( int i = 1; i < n - k + 1; i++) { y_prev = y; y = y->next; } // If x_prev exists, then new next of // it will be y. Consider the case // when y->next is x, in this case, // x_prev and y are same. So the statement // "x_prev->next = y" creates a self loop. // This self loop will be broken // when we change y->next. if (x_prev) x_prev->next = y; // Same thing applies to y_prev if (y_prev) y_prev->next = x; // Swap next pointers of x and y. // These statements also break self // loop if x->next is y or y->next is x Node* temp = x->next; x->next = y->next; y->next = temp; // Change head pointers when k is 1 or n if (k == 1) *head_ref = y; if (k == n) *head_ref = x; } // Driver program to test above functions int main() { // Let us create the following // linked list for testing // 1->2->3->4->5->6->7->8 struct Node* head = NULL; for ( int i = 8; i >= 1; i--) push(&head, i); cout << "Original Linked List: " ; printList(head); for ( int k = 1; k < 9; k++) { swapKth(&head, k); cout << "Modified List for k = " << k << endl; printList(head); } return 0; } |
JAVA
// A Java program to swap kth // node from the beginning with // kth node from the end class Node { int data; Node next; Node( int d) { data = d; next = null ; } } class LinkedList { Node head; /* Utility function to insert a node at the beginning */ void push( int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Utility function for displaying linked list */ void printList() { Node node = head; while (node != null ) { System.out.print(node.data + " " ); node = node.next; } System.out.println( "" ); } /* Utility function for calculating length of linked list */ int countNodes() { int count = 0 ; Node s = head; while (s != null ) { count++; s = s.next; } return count; } /* Function for swapping kth nodes from both ends of linked list */ void swapKth( int k) { // Count nodes in linked list int n = countNodes(); // Check if k is valid if (n < k) return ; // If x (kth node from start) and // y(kth node from end) are same if ( 2 * k - 1 == n) return ; // Find the kth node from beginning of linked list. // We also find previous of kth node because we need // to update next pointer of the previous. Node x = head; Node x_prev = null ; for ( int i = 1 ; i < k; i++) { x_prev = x; x = x.next; } // Similarly, find the kth node from end and its // previous. kth node from end is (n-k+1)th node // from beginning Node y = head; Node y_prev = null ; for ( int i = 1 ; i < n - k + 1 ; i++) { y_prev = y; y = y.next; } // If x_prev exists, then new next of it will be y. // Consider the case when y->next is x, in this case, // x_prev and y are same. So the statement // "x_prev->next = y" creates a self loop. This self // loop will be broken when we change y->next. if (x_prev != null ) x_prev.next = y; // Same thing applies to y_prev if (y_prev != null ) y_prev.next = x; // Swap next pointers of x and y. These statements // also break self loop if x->next is y or y->next // is x Node temp = x.next; x.next = y.next; y.next = temp; // Change head pointers when k is 1 or n if (k == 1 ) head = y; if (k == n) head = x; } // Driver code to test above public static void main(String[] args) { LinkedList llist = new LinkedList(); for ( int i = 8 ; i >= 1 ; i--) llist.push(i); System.out.print( "Original linked list: " ); llist.printList(); System.out.println( "" ); for ( int i = 1 ; i < 9 ; i++) { llist.swapKth(i); System.out.println( "Modified List for k = " + i); llist.printList(); System.out.println( "" ); } } } |
Python3
""" A Python3 program to swap kth node from the beginning with kth node from the end """ class Node: def __init__( self , data, next = None ): self .data = data self . next = next class LinkedList: def __init__( self , * args, * * kwargs): self .head = Node( None ) """ Utility function to insert a node at the beginning @args: data: value of node """ def push( self , data): node = Node(data) node. next = self .head self .head = node # Print linked list def printList( self ): node = self .head while node. next is not None : print (node.data, end = " " ) node = node. next # count number of node in linked list def countNodes( self ): count = 0 node = self .head while node. next is not None : count + = 1 node = node. next return count """ Function for swapping kth nodes from both ends of linked list """ def swapKth( self , k): # Count nodes in linked list n = self .countNodes() # check if k is valid if n<k: return """ If x (kth node from start) and y(kth node from end) are same """ if ( 2 * k - 1 ) = = n: return """ Find the kth node from beginning of linked list. We also find previous of kth node because we need to update next pointer of the previous. """ x = self .head x_prev = Node( None ) for i in range (k - 1 ): x_prev = x x = x. next """ Similarly, find the kth node from end and its previous. kth node from end is (n-k + 1)th node from beginning """ y = self .head y_prev = Node( None ) for i in range (n - k): y_prev = y y = y. next """ If x_prev exists, then new next of it will be y. Consider the case when y->next is x, in this case, x_prev and y are same. So the statement "x_prev->next = y" creates a self loop. This self loop will be broken when we change y->next. """ if x_prev is not None : x_prev. next = y # Same thing applies to y_prev if y_prev is not None : y_prev. next = x """ Swap next pointers of x and y. These statements also break self loop if x->next is y or y->next is x """ temp = x. next x. next = y. next y. next = temp # Change head pointers when k is 1 or n if k = = 1 : self .head = y if k = = n: self .head = x # Driver Code llist = LinkedList() for i in range ( 8 , 0 , - 1 ): llist.push(i) llist.printList() for i in range ( 1 , 9 ): llist.swapKth(i) print ( "Modified List for k = " , i) llist.printList() print ( "" ) # This code is contributed by Pulkit |
C#
// C# program to swap kth node from the beginning with // kth node from the end using System; public class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } public class LinkedList { Node head; /* Utility function to insert a node at the beginning */ void push( int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Utility function for displaying linked list */ void printList() { Node node = head; while (node != null ) { Console.Write(node.data + " " ); node = node.next; } Console.WriteLine( "" ); } /* Utility function for calculating length of linked list */ int countNodes() { int count = 0; Node s = head; while (s != null ) { count++; s = s.next; } return count; } /* Function for swapping kth nodes from both ends of linked list */ void swapKth( int k) { // Count nodes in linked list int n = countNodes(); // Check if k is valid if (n < k) return ; // If x (kth node from start) and y(kth node from end) // are same if (2 * k - 1 == n) return ; // Find the kth node from beginning of linked list. // We also find previous of kth node because we need // to update next pointer of the previous. Node x = head; Node x_prev = null ; for ( int i = 1; i < k; i++) { x_prev = x; x = x.next; } // Similarly, find the kth node from end and its // previous. kth node from end is (n-k+1)th node // from beginning Node y = head; Node y_prev = null ; for ( int i = 1; i < n - k + 1; i++) { y_prev = y; y = y.next; } // If x_prev exists, then new next of it will be y. // Consider the case when y->next is x, in this case, // x_prev and y are same. So the statement // "x_prev->next = y" creates a self loop. This self // loop will be broken when we change y->next. if (x_prev != null ) x_prev.next = y; // Same thing applies to y_prev if (y_prev != null ) y_prev.next = x; // Swap next pointers of x and y. These statements // also break self loop if x->next is y or y->next // is x Node temp = x.next; x.next = y.next; y.next = temp; // Change head pointers when k is 1 or n if (k == 1) head = y; if (k == n) head = x; } // Driver code public static void Main(String[] args) { LinkedList llist = new LinkedList(); for ( int i = 8; i >= 1; i--) llist.push(i); Console.Write( "Original linked list: " ); llist.printList(); Console.WriteLine( "" ); for ( int i = 1; i < 9; i++) { llist.swapKth(i); Console.WriteLine( "Modified List for k = " + i); llist.printList(); Console.WriteLine( "" ); } } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // A javascript program to swap kth // node from the beginning with // kth node from the end class Node { constructor(val) { this .data = val; this .next = null ; } } var head; /* * Utility function to insert a node at the beginning */ function push(new_data) { new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Utility function for displaying linked list */ function printList() { node = head; while (node != null ) { document.write(node.data + " " ); node = node.next; } document.write( "" ); } /* * Utility function for calculating length of linked list */ function countNodes() { var count = 0; s = head; while (s != null ) { count++; s = s.next; } return count; } /* * Function for swapping kth nodes from both ends of linked list */ function swapKth(k) { // Count nodes in linked list var n = countNodes(); // Check if k is valid if (n < k) return ; // If x (kth node from start) and // y(kth node from end) are same if (2 * k - 1 == n) return ; // Find the kth node from beginning of linked list. // We also find previous of kth node because we need // to update next pointer of the previous. x = head; x_prev = null ; for (i = 1; i < k; i++) { x_prev = x; x = x.next; } // Similarly, find the kth node from end and its // previous. kth node from end is (n-k+1)th node // from beginning y = head; y_prev = null ; for (i = 1; i < n - k + 1; i++) { y_prev = y; y = y.next; } // If x_prev exists, then new next of it will be y. // Consider the case when y->next is x, in this case, // x_prev and y are same. So the statement // "x_prev->next = y" creates a self loop. This self // loop will be broken when we change y->next. if (x_prev != null ) x_prev.next = y; // Same thing applies to y_prev if (y_prev != null ) y_prev.next = x; // Swap next pointers of x and y. These statements // also break self loop if x->next is y or y->next // is x temp = x.next; x.next = y.next; y.next = temp; // Change head pointers when k is 1 or n if (k == 1) head = y; if (k == n) head = x; } // Driver code to test above for (let i = 8; i >= 1; i--) push(i); document.write( "Original linked list: <br/>" ); printList(); document.write( "<br/>" ); for (let i = 1; i < 9; i++) { swapKth(i); document.write( "Modified List for k = " + i + "<br/>" ); printList(); document.write( "<br/>" ); } // This code is contributed by gauravrajput1 </script> |
输出：
Original Linked List: 1 2 3 4 5 6 7 8Modified List for k = 18 2 3 4 5 6 7 1Modified List for k = 28 7 3 4 5 6 2 1Modified List for k = 38 7 6 4 5 3 2 1Modified List for k = 48 7 6 5 4 3 2 1Modified List for k = 58 7 6 4 5 3 2 1Modified List for k = 68 7 3 4 5 6 2 1Modified List for k = 78 2 3 4 5 6 7 1Modified List for k = 81 2 3 4 5 6 7 8
复杂性分析：
- 时间复杂性： O（n），其中n是列表的长度。 需要遍历列表一次。
- 辅助空间： O（1）。 不需要额外的空间。
请注意，上面的代码运行三个单独的循环来计算节点，查找x和x prev，以及查找y和y_prev。这三件事可以在一个循环中完成。代码使用了三个循环来保持简单易读。 幸亏 钱德拉·普拉卡什 对于初始解决方案。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
