PTA（链表）1-10 单链表分段逆转

1-10 单链表分段逆转

分数 6

作者 陈越

单位 浙江大学

给定一个带头结点的单链表和一个整数K，要求你将链表中的每K个结点做一次逆转。例如给定单链表 1→2→3→4→5→6 和 K=3，你需要将链表改造成 3→2→1→6→5→4；如果 K=4，则应该得到 4→3→2→1→5→6。

函数接口定义：

1
void K_Reverse( List L, int K );

其中List结构定义如下：

1
2
3
4
5
6
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定的带头结点的单链表，K是每段的长度。函数K_Reverse应将L中的结点按要求分段逆转。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

List ReadInput(); /* 裁判实现，细节不表 */
void PrintList( List L ); /* 裁判实现，细节不表 */
void K_Reverse( List L, int K );

int main()
{
    List L;
    int K;

    L = ReadInput();
    scanf("%d", &K);
    K_Reverse( L, K );
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

1
2
3
6
1 2 3 4 5 6
4

输出样例：

1
4 3 2 1 5 6

解析

此题依旧是一头雾水，如果单链表的逆转（用到三指针）不会的话先去看看PTA（链表）1-2 单链表逆转 | zhangzhang-blog

此题是在这个的基础上的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
void K_Reverse( List L, int K )
{
    if (K <= 1) {
        // K <= 1 时无需逆转
        return;
    }

    // PreTail: 总是指向当前要逆转段的前一个结点（即上一段的尾结点或头结点 L）
    PtrToNode PreTail = L;

    while (1) {
        // 1. 检查当前段是否有 K 个结点
        PtrToNode check_ptr = PreTail->Next;
        int count = 0;
        for (int i = 0; i < K; i++) {
            if (check_ptr == NULL) {
                // 不足 K 个，本段及后续不逆转
                return;
            }
            check_ptr = check_ptr->Next;
            count++;
        }

        // 此时 count == K，确定有 K 个结点需要逆转

        // NewTail: 逆转后新段的尾结点 (即逆转前的头结点)
        PtrToNode NewTail = PreTail->Next;

        // Current: 用于逆转操作的当前结点
        PtrToNode Current = NewTail;

        // NextHead: 逆转后下一段的头结点 (即逆转前第 K+1 个结点)
        PtrToNode NextHead = check_ptr; // check_ptr 在循环结束后指向第 K+1 个结点

        // 逆转 K 个结点的标准三指针方法
        PtrToNode prev = NextHead; // prev 初始化为下一段的头结点 (作为逆转后的新头结点的Next)
        PtrToNode curr = Current;
        PtrToNode next = NULL;

        // 逆转 K 个结点
        for (int i = 0; i < K; i++) {
            next = curr->Next;
            curr->Next = prev;
            prev = curr;
            curr = next;
        }

        // 3. 连接新的段
        // prev 现在指向逆转后的新段的头结点 (即原段的第 K 个结点)

        // 将上一段的尾结点连接到逆转后的新段的头结点
        PreTail->Next = prev;

        // 4. 更新 PreTail 到新逆转段的尾结点
        // NewTail 是逆转后的尾结点
        PreTail = NewTail;
    }
}

示意图

1.初始状态

image-20251020185153733

2.跟单链表的逆转一样了（三指针）

K=3,i=0时如下图

image-20251020185212984

K=3,i=1时如下图

image-20251019100643482

K=3,i=2时如下图

image-20251020185257716

PreTail->Next = prev;

image-20251020185310988

算法思路

  1. 分段遍历与定位: 使用一个指针 PreTail 始终指向当前段逆转前的头结点（即上一段的尾结点或整个链表的头结点）。初始时，PreTail 指向链表的头结点 $L$。
  2. 检查段长: 在开始逆转一段之前，先从 PreTail->Next 开始向后检查 $K$ 个结点是否存在。如果不存在 $K$ 个结点，则这段不进行逆转，直接退出循环。
  3. 定位段的头部和尾部:
    • NewTail: 逆转后新段的尾结点，即逆转前老段的头结点 PreTail->Next。
    • Current: 用于遍历 $K$ 个结点，并辅助逆转操作。
    • NextHead: 逆转后新段的头结点（即逆转前老段的第 $K$ 个结点）。
  4. $K$ 个结点的原地逆转:
    • 逆转操作在 $K$ 个结点内部进行。我们采用头插法的思想进行原地逆转，或者使用三个指针 (prev, curr, next) 的标准链表逆转方法。
    • 这里我们采用标准逆转法：
      • prev 初始化为 nullptr (或 NULL)。
      • curr 初始化为 NewTail。
      • 循环 $K$ 次，将 curr 的 Next 指针指向 prev，然后更新 prev 和 curr。
  5. 连接新的段:
    • 逆转完成后，prev 将指向逆转后的新段的头结点 NextHead。（这样下一次curr->next = prev,可以让此次尾部连接下一次的反转的头部）
    • NewTail（逆转前的头结点）现在是逆转后的尾结点，它的 Next 应该连接到下一段的头结点。这个下一段的头结点就是逆转开始前 Current（循环 $K$ 次后的下一个结点）。
    • PreTail（上一段的尾结点）的 Next 应该指向逆转后的新段的头结点 NextHead (prev)。
    • 更新 PreTail 指向新逆转段的尾结点，即 NewTail，以便开始下一段的逆转。

做题：先定义Pretail，判断是否满足K个，不满足就退出，再定义NewTail，Current，NextHead，这是找此次反转的头部和尾部，再就是反转该链表，用的是三指针法