A1074: Reversing Linked List

Author: CHEN, Yue
Organization: 浙江大学
Time Limit: 400 ms
Memory Limit: 64 MB
Code Size Limit: 16 KB

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤ 10^​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

题目意思

将链表分为 K 组，然后对其中的每一组（每组必须有 K 个元素）进行反转，对于最后一组若不满 K 个节点，则不进行反转操作。

题目分析

从算法笔记上看到的方案比较繁琐，笔者通过递归的方法来进行链表的反转。同时，在这里采用静态链表形式来存储链表。

最重要的代码是在 reverse() 部分，其中的逻辑很简单：

  1. 找到第 k 个节点的后面的那个元素，因为那个元素是新的递归的 head 节点；
int kNext = head;
for(int i = 0; i < k; i++) {
    kNext = lists[kNext].next;
    if(kNext == -1 && i < k - 1) {
        return head;
    }
}

如果该组节点的个数小于 k 个，那么就直接返回当前组的头节点，且不进行反转操作。

  1. 从 head 开始进行反转，直到当前节点的 next 节点是第 k 个节点，这个时候第 k 个节点就是这一组节点中的头节点，而 head 节点反而是这组节点的尾节点；

链表反转的主要代码如下：

int current = head;
int prev = kNext;
while(current != kNext) {
    int next = lists[current].next;
    lists[current].next = prev;
    prev = current;
    current = next;
}
  1. 如何将一个分组（非最后一个分组）的尾节点和下一个分组的头节点进行关联是一个关键点，否则将造成最后反转的结果是紊乱的。于是我们考虑将reverser() 的返回值设置为本组节点反转之后的头节点，那么在递归调用 reverse() 之后呢需要将本组节点反转之后的尾节点和递归调用的结果（上一组节点反转之后的头节点）进行关联。
lists[head].next= reverse(kNext, k)

注意：关联操作一定要在递归调用 reverse() 之后进行，因为每组节点进行反转之后的结果都是变化的，如果不及时更改上一组的尾节点所指向的下一个节点，将会造成错误。

题目解答

https://github.com/JohnNiang/algorithm/blob/master/A1074/main.cpp

#include <iostream>
#include <algorithm>

using namespace std;

// A1074: Reversing Linked List
// <https://pintia.cn/problem-sets/994805342720868352/problems/994805394512134144>

const int MAX = 100000;

struct LinkedList {
    int data;
    int next;
    int address;
} lists[MAX];

void print(LinkedList& list) {
    printf("%05d %d", list.address, list.data);
    if(list.next != -1) {
        printf(" %05d", list.next);
    } else {
        printf(" %d", list.next);
    }

    printf("\n");
}

void print(int head) {
    int current = head;
    while(current != -1) {
        LinkedList list = lists[current];
        print(list);
        current = list.next;
    }
}

int reverse(int head, int k) {
    if(head == -1) {
        return head;
    }
    int kNext = head;
    for(int i = 0; i < k; i++) {
        kNext = lists[kNext].next;
        if(kNext == -1 && i < k - 1) {
            return head;
        }
    }
    int current = head;
    int prev = kNext;
    while(current != kNext) {
        int next = lists[current].next;
        lists[current].next = prev;
        prev = current;
        current = next;
    }
    lists[head].next= reverse(kNext, k);
    return prev;
}

int main() {

    int head = 0;
    int N = 0;
    int K = 0;
    cin >> head >> N >> K;
    for(int i = 0; i < N; i++) {
        int address = 0;
        cin >> address;
        cin >> lists[address].data >> lists[address].next;
        lists[address].address = address;
    }
    head = reverse(head, K);
    print(head);
    return 0;
}