将N个链接列表节点移到前面（C）

Here's a problem I'm having some trouble with in C. So, we have a function with two parameters:

这是一个问题我在C中遇到了一些问题。所以,我们有一个带有两个参数的函数:

1. struct list ** ptrptr

struct list ** ptrptr

2. int K

K represents the number of Nodes that we have to shift from the end to the beginning of the list, like this:

K表示我们必须从列表的末尾切换到开头的节点数,如下所示:

I know how to shift one element, but I can't wrap my head around using tmps to solve with K nodes.

我知道如何移动一个元素,但我不能用tmps来解决K节点。

I would appreciate any suggestion. Here's the code for one node.

我将不胜感激任何建议。这是一个节点的代码。

void Shift(node **head){
   node *prev;
   node *curr = *head;
   while(curr != NULL && curr->next != NULL) {
      prev = curr;
      curr = curr->next;
   }
   prev->next = NULL;
   curr->next = *head;
   *head = curr;

}

2 个解决方案

#1

You can shift a complete chain of K nodes in a single "step". Suppose the list consists of N elements, that nmk is the node at position N-K, and that e is the last node of the list. Then the code would be...

您可以在一个“步骤”中移动完整的K个节点链。假设列表由N个元素组成,即nmk是位置N-K处的节点,并且e是列表的最后一个节点。那么代码就是......

e->next = *head;
*head = nmk->next;
nmk->next = NULL;

The trick will now be to find node nmk, but I leave this up to you if you don't mind :-) And don't forget to check corner cases like empty lists, N==K, ....

现在的诀窍就是找到节点nmk,但是如果你不介意的话我会把它留给你:-)并且不要忘记检查像空列表这样的角落情况,N == K,....

#2

// Shift the last N nodes of a linked list to the front of
// the list, preserving node order within those N nodes.
//
// Returns -1 if there are not enough nodes, -2 for invalid N,
// 0 otherwise
int shift(list_t **head, int n) {
    list_t *t1, *t2;
    int i;

    if ((head == NULL) || (*head == NULL))
        return -1;

    if (n <= 0)
        return -2;

    // move initial pointer ahead n steps
    t1 = *head;
    for (i = 0; i < n; i++) {
        t1 = t1->next;
        if (t1 == NULL) {
            return -1;
        }
    }

    t2 = *head;

    // t2 and t1 are now N nodes away from each other.
    // When t1 gets to the last node, t2 will point
    // to the node previous to the last N nodes.
    while (t1->next != NULL) {
        t1 = t1->next;
        t2 = t2->next;
    }

    // move the end nodes to the front of the list
    t1->next = *head;
    *head = t2->next;
    t2->next = NULL;

    return 0;
}