C语言技术咨询：如何将链表末尾K个节点移至头部

首先，你已经搞定了单个节点的移动，这很棒！其实扩展到K个节点的核心是一次性定位到需要截断的位置，而不是循环K次调用单节点移动（后者时间复杂度会更高，是O(K*N)，我们可以做到O(N)的单次遍历）。

核心思路拆解 #

我们可以按这几步来：

• 先处理边界情况：如果链表为空、只有1个节点，或者K=0，直接返回即可，无需操作。
• 计算链表总长度：这样可以处理K大于链表长度的情况（比如K=5但链表只有3个节点，实际等价于K=5%3=2），避免做无用功。
• 定位截断点：找到倒数第K+1个节点（记为prev_tail），它后面的K个节点就是要移到头部的部分。比如链表1->2->3->4->5，K=2时，倒数第3个节点是3，后面的4->5就是我们要移动的目标。
• 调整指针完成移动：把截断点后的部分从原链表断开，然后将这部分的尾部连接到原链表头部，最后更新链表头部为移动部分的第一个节点。

代码实现 #

结合你的代码风格，我写了一份完整的实现：

#include <stdio.h>
#include <stdlib.h>

// 假设你的节点结构是这样的（如果和你的定义不同，替换成你的即可）
typedef struct list {
    int data;
    struct list *next;
} node;

void ShiftK(node **ptrptr, int K) {
    // 边界情况处理
    if (*ptrptr == NULL || (*ptrptr)->next == NULL || K <= 0) {
        return;
    }

    node *curr = *ptrptr;
    int len = 0;

    // 第一步：计算链表总长度
    while (curr != NULL) {
        len++;
        curr = curr->next;
    }

    // 处理K大于链表长度的情况，取模得到实际需要移动的数量
    K = K % len;
    // 如果取模后K为0，说明不需要移动
    if (K == 0) {
        return;
    }

    // 第二步：找到倒数第K+1个节点
    curr = *ptrptr;
    for (int i = 0; i < len - K - 1; i++) {
        curr = curr->next;
    }
    node *prev_tail = curr;
    // 要移动的部分的头节点
    node *new_head = prev_tail->next;
    // 找到要移动部分的尾节点
    node *tail = new_head;
    while (tail->next != NULL) {
        tail = tail->next;
    }

    // 第三步：调整指针
    prev_tail->next = NULL;       // 断开原链表和移动部分的连接
    tail->next = *ptrptr;         // 移动部分的尾连到原头部
    *ptrptr = new_head;           // 更新链表头部为移动部分的头
}

// 辅助函数：打印链表，用于测试
void printList(node *head) {
    node *curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

// 测试用例
int main() {
    // 创建链表 1->2->3->4->5
    node *head = (node*)malloc(sizeof(node));
    head->data = 1;
    head->next = (node*)malloc(sizeof(node));
    head->next->data = 2;
    head->next->next = (node*)malloc(sizeof(node));
    head->next->next->data = 3;
    head->next->next->next = (node*)malloc(sizeof(node));
    head->next->next->next->data = 4;
    head->next->next->next->next = (node*)malloc(sizeof(node));
    head->next->next->next->next->data = 5;
    head->next->next->next->next->next = NULL;

    printf("原链表：");
    printList(head);

    ShiftK(&head, 2);
    printf("移动2个节点后：");
    printList(head);

    ShiftK(&head, 6); // K=6，等价于6%5=1
    printf("再移动6个节点后：");
    printList(head);

    return 0;
}

和你现有单节点代码的对比 #

你写的Shift函数，本质是找倒数第2个节点（prev），然后把最后1个节点移到头部。而ShiftK函数是把这个逻辑扩展：找倒数第K+1个节点，把后面K个节点作为一个整体移动，这样只需要遍历链表2次（一次算长度，一次找截断点），比循环K次调用Shift高效得多。

额外提示 #

• 如果不想遍历两次链表，也可以用快慢指针：先让快指针走K步，然后快慢指针一起走，直到快指针到尾，此时慢指针就是倒数第K+1个节点，这样可以把时间复杂度的常数项降低。
• 一定要注意处理K为0、K大于链表长度这些边界情况，否则容易出现空指针错误。

内容的提问来源于stack exchange，提问作者Arrigo Lupori