K 节点组中的链表反转

Question

一开始面试官问的是反转链表的问题，我很容易就解决了
现在他说以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;
}

Answer 1

> 它给出了整个列表的输出反转....

这是因为下次控制进入这个if块时

if(counter == k)

指针 prevPtr 仍然指向列表中的相同节点，它在操作列表时在上一次迭代中指向相同的节点。您需要在反转一组 k 节点时将 prevPtr 设置为 NULL。除此之外，您还需要明确处理列表的 head 和 tail。列表的 head 将是第一组 k 节点的第 k^th 个节点，列表的 tail 将是当列表中的节点是k的倍数时，最后一组k节点的第一个节点，或者当列表中的节点不是[的倍数时，它将指向剩余列表的第一个节点=17=]。在反转每组 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;
}

Answer 2

Initially, the interviewer asked the question to reverse the linked list which I solved easily. Now he said to reverse the list in group of K nodes.

首先，从不在面试中做任何测试作业。不要让别人操纵你和你的时间。忽略此类提供测试任务的公司。

至于任务，例如，使用递归函数不是一个好主意，因为对于大列表，您可能会出现堆栈溢出。

另外再引入一种结构来声明列表本身会更好。

我可以建议以下解决方案。

#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

Answer 3

你的方法没问题，但你没有 link 正确地对反向列表进行分段：

您可以因式分解 fastPtr = fastPtr->next;，因为它在 if 语句的两个分支中执行。
最后一个节点的测试是伪造的：如果列表长度是 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;
}

输出：

reverseKGroup(0): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverseKGroup(1): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
reverseKGroup(2): 2, 1, 4, 3, 6, 5, 8, 7, 10, 9
reverseKGroup(3): 3, 2, 1, 6, 5, 4, 9, 8, 7, 10
reverseKGroup(4): 4, 3, 2, 1, 8, 7, 6, 5, 9, 10
reverseKGroup(5): 5, 4, 3, 2, 1, 10, 9, 8, 7, 6
reverseKGroup(6): 6, 5, 4, 3, 2, 1, 7, 8, 9, 10
reverseKGroup(7): 7, 6, 5, 4, 3, 2, 1, 8, 9, 10
reverseKGroup(8): 8, 7, 6, 5, 4, 3, 2, 1, 9, 10
reverseKGroup(9): 9, 8, 7, 6, 5, 4, 3, 2, 1, 10
reverseKGroup(10): 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
reverseKGroup(11): 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

K 节点组中的链表反转

Linked list reversed in groups of K nodes

c

algorithm

reverse

linked-list

singly-linked-list