最初，面试官问了我很容易解决的链表的问题.
现在他说要反转K节点组的列表。
例如，如果列表[1,2,3,4,5,6]且K=4则o/p = [4,3,2,1,5,6].。所以我修改了现有的解决方案来实现它，但它仍然颠倒了整个列表的输出(i.e [6,5,4,3,2,1])。请参阅下面的程序。可能需要一些小的更改，但我无法弄清楚。谁能帮助哪里有问题？
ListNode *reverseKGroup(ListNode *head, int k)
{
if (k == 0 || k == 1)
return head;
if (head == NULL)
return NULL;
int counter = 0;
ListNode *fastPtr = head;
ListNode *currentPtr = head;
ListNode *nextPtr = NULL;
ListNode *prevPtr = NULL;
while (fastPtr)
{
counter++;
//one chain formed from list, reverse it
if (counter == k)
{
fastPtr = fastPtr->next;
while (counter)
{
nextPtr = currentPtr->next;
currentPtr->next = prevPtr;
prevPtr = currentPtr;
currentPtr = nextPtr;
counter--;
}
//last node
if (currentPtr->next == NULL)
{
currentPtr->next = prevPtr;
prevPtr = currentPtr;
break;
}
}
else
{
fastPtr = fastPtr->next;
}
}
return prevPtr;
}
您的方法没问题，但是您没有正确链接反向列表片段：
-
您可以在
if语句的两个分支中执行fastPtr = fastPtr->next;时对其进行分解。 -
最后一个节点的测试是假的：如果列表长度是
k的倍数，if (currentPtr->next == NULL)将取消引用空指针。 -
相反，您应该保留一个指针，指向存储反向列表片段头部的位置。在循环开始时，此指针指向变量
head，并且在每次片段反转后，它应该指向反转前片段第一个节点的next成员，即反转循环开始时的CurrentNode值。
通过这些小的修改，您的代码可以正常运行。
请注意，这个问题很棘手。如果面试官要求你以互动方式解决问题，他们可能对你解决问题的方法感兴趣。在不到半小时的时间内构建一个有效而优雅的解决方案将是非常好的。
这是带有测试平台的修改版本：
#include <stdio.h>
typedef struct ListNode {
struct ListNode *next;
int data;
} ListNode;
ListNode *reverseKGroup(ListNode *head, int k) {
if (k > 1) { // no need to test for `head != NULL`
int counter = 0;
ListNode **start = &head; // place where to store the head of the reversed fragment
ListNode *currentPtr = head; // pointer to the first node of the fragment
ListNode *fastPtr = head; // pointer to the node after the end of the fragment
while (fastPtr) {
fastPtr = fastPtr->next;
counter++;
if (counter == k) {
// k nodes between CurrentPtr and fastPtr: reverse the fragment
ListNode *lastPtr = currentPtr;
ListNode *prevPtr = fastPtr;
while (counter) {
ListNode *nextPtr = currentPtr->next;
currentPtr->next = prevPtr;
prevPtr = currentPtr;
currentPtr = nextPtr;
counter--;
}
*start = prevPtr;
start = &lastPtr->next;
}
}
}
return head;
}
void printList(const char *prefix, const ListNode *p, const char *suffix) {
while (p) {
printf("%s%d", prefix, p->data);
prefix = ", ";
p = p->next;
}
printf("%s", suffix);
}
ListNode *test(ListNode *list, int k) {
printf("reverseKGroup(%d): ", k);
list = reverseKGroup(list, k);
printList("", list, "n");
return reverseKGroup(list, k); // undo k-reversal
}
int main() {
ListNode a[10], *list = a;
for (int i = 0; i < 10; i++) {
a[i].next = i + 1 < 10 ? &a[i + 1] : NULL;
a[i].data = i + 1;
}
for (int k = 0; k <= 11; k++) {
list = test(list, k);
}
return 0;
}
输出：
反向组(0)： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10 反向组(1)： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10 反向组(2)： 2， 1， 4， 3， 6， 5， 8， 7， 10， 9 反向组(3)： 3， 2， 1， 6， 5， 4， 9， 8， 7， 10 反向组(4)： 4， 3， 2， 1， 8， 7， 6， 5， 9， 10 反向组(5)： 5， 4， 3， 2， 1， 10， 9， 8， 7， 6 反向组(6)： 6， 5， 4， 3， 2， 1， 7， 8， 9， 10 反向组(7)： 7， 6， 5， 4， 3， 2， 1， 8， 9， 10 反向组(8)： 8， 7， 6， 5， 4， 3， 2， 1， 9， 10 反向组(9)： 9， 8， 7， 6， 5， 4， 3， 2， 1， 10 反向组(10)： 10， 9， 8， 7， 6， 5， 4， 3， 2， 1 反向组(11)： 1， 2， 3， 4， 5， 6， 7， 8， 9， 10
>它给出了整个列表的输出颠倒....
这是因为下次控件进入此if块时
if(counter == k)
指针prevPtr在操作列表时仍指向列表中它在上一次迭代中指向的相同节点。您需要将prevPtr设置为NULL，同时反转一组k节点。除此之外，您还需要明确处理列表的head和tail。列表的head将是反转的第一组k节点的第k个节点，当列表中的节点是k的倍数时，列表的tail将是最后一组k节点的第一个节点，或者当列表中的节点不在k的倍数时，它将指向剩余列表的第一个节点。在反转每组k节点时，需要注意列表的tail。
粗略修改了您的代码，并处理了上述细节：
ListNode* reverseKGroup(ListNode* head, int k)
{
if(k==0 || k==1)
return head;
if(head == NULL)
return NULL;
int counter = 0;
ListNode* fastPtr = head;
ListNode* currentPtr = head;
ListNode* nextPtr = NULL;
ListNode* prevPtr = NULL;
ListNode* tail = NULL;
ListNode* currLast = NULL;
int set_head = 0;
int set_currLast = 0;
while(fastPtr)
{
counter++;
//one chain formed from list, reveser it
if(counter == k)
{
fastPtr = fastPtr->next;
prevPtr = NULL;
set_currLast = 0;
while(counter)
{
nextPtr = currentPtr->next;
currentPtr->next = prevPtr;
// when reversing group of k nodes, the first node will be
// the last when whole group reversed
if (!set_currLast)
{
currLast = currentPtr;
set_currLast = 1;
}
prevPtr = currentPtr;
currentPtr = nextPtr;
counter--;
}
// Need to set head just once only
if (!set_head) {
tail = head;
head = prevPtr;
set_head = 1;
} else {
// the tail need to set after reversing every k nodes group
tail->next = prevPtr;
tail = currLast;
}
// For the last group which will be of size less than k
tail->next = nextPtr;
}
else
{
fastPtr = fastPtr->next;
}
}
return head;
}
可以使用递归来反转列表中的k个节点组中的节点。代码看起来很干净，更容易理解：
struct ListNode * revll(struct ListNode *head, int k) {
struct ListNode * prev = NULL;
struct ListNode * curr = head;
struct ListNode * tmp = NULL;
int count = k;
tmp = head;
while (tmp && count) {
count--;
tmp = tmp->next;
}
if (count != 0) {
return head;
}
while ((curr != NULL) && (count < k)) {
tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
count++;
}
if (tmp) {
head->next = revll(tmp, k);
}
return prev;
}
最初，面试官提出问题以反转链接 我很容易解决的列表。现在他说要把名单反转成组 的 K 个节点。
首先，从不在面试中做任何测试作业。不要让别人操纵你和你的时间。忽略那些提供测试任务的公司。
至于任务，例如，使用递归函数不是一个好主意，因为对于大列表，您可能会获得堆栈溢出。
此外，引入另一种结构来声明列表本身会好得多。
我可以建议以下解决方案。
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int data;
struct Node *next;
};
struct List
{
struct Node *head;
};
int push_front( struct List *list, int data )
{
struct Node *new_node = malloc( sizeof( struct Node ) );
int success = new_node != NULL;
if ( success )
{
new_node->data = data;
new_node->next = list->head;
list->head = new_node;
}
return success;
}
void clear( struct List *list )
{
while ( list->head != NULL )
{
struct Node *tmp = list->head;
list->head = list->head->next;
free( tmp );
}
}
FILE * display( const struct List *list, FILE *fp )
{
for ( const struct Node *current = list->head; current != NULL; current = current->next )
{
fprintf( fp, "%d -> ", current->data );
}
fputs( "null", fp );
return fp;
}
void reverse_n( struct List *list, size_t n )
{
if ( !( n < 2 ) )
{
for( struct Node **first = &list->head, *last = list->head; last != NULL; )
{
for ( size_t i = n; --i != 0 && last; )
{
last = last->next;
}
if ( last != NULL )
{
struct Node *next = ( *first )->next;
( *first )->next = last->next;
last = *first;
for ( size_t i = n; --i != 0; )
{
struct Node *tmp = next;
next = next->next;
tmp->next = *first;
*first = tmp;
}
first = &last->next;
last = last->next;
}
}
}
}
int main(void)
{
struct List list = { .head = NULL };
const int N = 10;
for ( size_t i = 2; i < N + 1; i++ )
{
for ( int j = N; j != 0; --j )
{
push_front( &list, j - 1 );
}
putc( 'n', display( &list, stdout ) );
reverse_n( &list, i );
putc( 'n', display( &list, stdout ) );
putc( 'n', stdout );
clear( &list );
}
return 0;
}
程序输出为
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
1 -> 0 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 9 -> 8 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
2 -> 1 -> 0 -> 5 -> 4 -> 3 -> 8 -> 7 -> 6 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
3 -> 2 -> 1 -> 0 -> 7 -> 6 -> 5 -> 4 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
4 -> 3 -> 2 -> 1 -> 0 -> 9 -> 8 -> 7 -> 6 -> 5 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 6 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> null