给定一个链表，编写一个函数来反转每k个节点（其中k是该函数的输入）。
null
例子：
输入 ：1->2->3->4->5->6->7->8->NULL，K=3 输出 ：3->2->1->6->5->4->8->7->NULL 输入 ：1->2->3->4->5->6->7->8->NULL，K=5 输出 ：5->4->3->2->1->8->7->6->NULL
算法 : 颠倒 （头，k）
- 反转大小k的第一个子列表。反转时跟踪下一个节点和上一个节点。让指向下一个节点的指针 下一个 和指向上一个节点的指针 上 看见 这篇帖子 用于反转链接列表。
- 头部->下一步=反向（下一步，k） （递归调用列表的其余部分并链接两个子列表）
- 回来 上 ( 上 成为列表的新头号人物（参见迭代方法的图表） 这篇帖子 )
下图显示了反转功能的工作原理：
![图片[1]-在给定大小的组中反转链表|集1-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/cdn-uploads/20190624113820/ReverseALinkedListInAGroupofGivenSize1.png)
以下是上述方法的实施情况：
C++
// CPP program to reverse a linked list // in groups of given size #include <bits/stdc++.h> using namespace std; /* Link list node */ class Node { public : int data; Node* next; }; /* Reverses the linked list in groups of size k and returns the pointer to the new head node. */ Node* reverse(Node* head, int k) { // base case if (!head) return NULL; Node* current = head; Node* next = NULL; Node* prev = NULL; int count = 0; /*reverse first k nodes of the linked list */ while (current != NULL && count < k) { next = current->next; current->next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if (next != NULL) head->next = reverse(next, k); /* prev is new head of the input list */ return prev; } /* UTILITY FUNCTIONS */ /* Function to push a node */ 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 linked list */ void printList(Node* node) { while (node != NULL) { cout << node->data << " " ; node = node->next; } } /* Driver code*/ int main() { /* Start with the empty list */ Node* head = NULL; /* Created Linked list is 1->2->3->4->5->6->7->8->9 */ push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); cout << "Given linked list " ; printList(head); head = reverse(head, 3); cout << "Reversed Linked list " ; printList(head); return (0); } // This code is contributed by rathbhupendra |
C
// C program to reverse a linked list in groups of given size #include<stdio.h> #include<stdlib.h> /* Link list node */ struct Node { int data; struct Node* next; }; /* Reverses the linked list in groups of size k and returns the pointer to the new head node. */ struct Node *reverse ( struct Node *head, int k) { if (!head) return NULL; struct Node* current = head; struct Node* next = NULL; struct Node* prev = NULL; int count = 0; /*reverse first k nodes of the linked list */ while (current != NULL && count < k) { next = current->next; current->next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if (next != NULL) head->next = reverse(next, k); /* prev is new head of the input list */ return prev; } /* UTILITY FUNCTIONS */ /* Function to push a node */ 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 linked list */ void printList( struct Node *node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver code*/ int main( void ) { /* Start with the empty list */ struct Node* head = NULL; /* Created Linked list is 1->2->3->4->5->6->7->8->9 */ push(&head, 9); push(&head, 8); push(&head, 7); push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); printf ( "Given linked list " ); printList(head); head = reverse(head, 3); printf ( "Reversed Linked list " ); printList(head); return (0); } |
JAVA
// Java program to reverse a linked list in groups of // given size class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node( int d) { data = d; next = null ; } } Node reverse(Node head, int k) { if (head == null ) return null ; Node current = head; Node next = null ; Node prev = null ; int count = 0 ; /* Reverse first k nodes of linked list */ while (count < k && current != null ) { next = current.next; current.next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if (next != null ) head.next = reverse(next, k); // prev is now head of input list return prev; } /* 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 */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; 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[]) { LinkedList llist = new LinkedList(); /* Constructed Linked List is 1->2->3->4->5->6-> 7->8->8->9->null */ llist.push( 9 ); llist.push( 8 ); llist.push( 7 ); llist.push( 6 ); llist.push( 5 ); llist.push( 4 ); llist.push( 3 ); llist.push( 2 ); llist.push( 1 ); System.out.println( "Given Linked List" ); llist.printList(); llist.head = llist.reverse(llist.head, 3 ); System.out.println( "Reversed list" ); llist.printList(); } } /* This code is contributed by Rajat Mishra */ |
蟒蛇3
# Python program to reverse a # linked list in group of given size # Node class class Node: # Constructor to initialize the node object def __init__( self , data): self .data = data self . next = None class LinkedList: # Function to initialize head def __init__( self ): self .head = None def reverse( self , head, k): if head = = None : return None current = head next = None prev = None count = 0 # Reverse first k nodes of the linked list while (current is not None and count < k): next = current. next current. next = prev prev = current current = next count + = 1 # next is now a pointer to (k+1)th node # recursively call for the list starting # from current. And make rest of the list as # next of first node if next is not None : head. next = self .reverse( next , k) # prev is new head of the input list return prev # Function to insert a new node at the beginning def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node # Utility function to print the linked LinkedList def printList( self ): temp = self .head while (temp): print (temp.data,end = ' ' ) temp = temp. next # Driver program llist = LinkedList() llist.push( 9 ) llist.push( 8 ) llist.push( 7 ) llist.push( 6 ) llist.push( 5 ) llist.push( 4 ) llist.push( 3 ) llist.push( 2 ) llist.push( 1 ) print ( "Given linked list" ) llist.printList() llist.head = llist.reverse(llist.head, 3 ) print ( "Reversed Linked list" ) llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program to reverse a linked list // in groups of given size using System; public class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } Node reverse(Node head, int k) { if (head == null ) return null ; Node current = head; Node next = null ; Node prev = null ; int count = 0; /* Reverse first k nodes of linked list */ while (count < k && current != null ) { next = current.next; current.next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if (next != null ) head.next = reverse(next, k); // prev is now head of input list return prev; } /* 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 */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ void printList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } /* Driver code*/ public static void Main(String[] args) { LinkedList llist = new LinkedList(); /* Constructed Linked List is 1->2->3->4->5->6-> 7->8->8->9->null */ llist.push(9); llist.push(8); llist.push(7); llist.push(6); llist.push(5); llist.push(4); llist.push(3); llist.push(2); llist.push(1); Console.WriteLine( "Given Linked List" ); llist.printList(); llist.head = llist.reverse(llist.head, 3); Console.WriteLine( "Reversed list" ); llist.printList(); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program to reverse a // linked list in groups of // given size var head; // head of list /* Linked list Node */ class Node { constructor(val) { this .data = val; this .next = null ; } } function reverse(head , k) { if (head == null ) return null ; var current = head; var next = null ; var prev = null ; var count = 0; /* Reverse first k nodes of linked list */ while (count < k && current != null ) { next = current.next; current.next = prev; prev = current; current = next; count++; } /* next is now a pointer to (k+1)th node Recursively call for the list starting from current. And make rest of the list as next of first node */ if (next != null ) head.next = reverse(next, k); // prev is now head of input list return prev; } /* Utility functions */ /* Inserts a new Node at front of the list. */ function push(new_data) { /* 1 & 2: Allocate the Node & Put in the data */ new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* Function to print linked list */ function printList() { temp = head; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } document.write( "<br/>" ); } /* Driver program to test above functions */ /* Constructed Linked List is 1->2->3->4->5->6-> 7->8->8->9->null */ push(9); push(8); push(7); push(6); push(5); push(4); push(3); push(2); push(1); document.write( "Given Linked List<br/>" ); printList(); head = reverse(head, 3); document.write( "Reversed list<br/>" ); printList(); // This code contributed by gauravrajput1 </script> |
输出：
Given Linked List1 2 3 4 5 6 7 8 9 Reversed list3 2 1 6 5 4 9 8 7
复杂性分析：
- 时间复杂性： O（n）。 列表遍历只执行一次，并且它有’n’个元素。
- 辅助空间： O（不适用）。 对于大小为n、n/k或（n/k）+1的每个链表，将在递归期间进行调用。
如果您发现上述代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
