循环单链表就地逆置

循环单链表就地逆置的步骤如下：

1. 判断链表是否为空，若为空则直接返回。
2. 定义三个指针pre、p、succ，分别指向链表的前一个节点、当前节点和后一个节点。
3. 将p指向第一个节点，pre指向最后一个节点。
4. 循环遍历链表，直到p指向pre，每次将p的后继指针指向pre，并将p、pre和succ分别向前移动一个节点。
5. 当p指向pre时，将p的后继指针指向pre，并将p、pre和succ分别向前移动一个节点。
6. 最后将链表的头节点指向pre，完成链表的就地逆置。

下面是 C++ 代码实现：

void reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }
    ListNode* pre = head;
    ListNode* p = head->next;
    ListNode* succ = p->next;
    while (p != head) {
        p->next = pre;
        pre = p;
        p = succ;
        succ = succ->next;
    }
    p->next = pre;
    head->next = succ;
    head = pre;
}

相关问题

用类C语言设计算法实现循环单链表就地逆置

循环单链表指的是最后一个节点的指针指向第一个节点，而且每个节点都有一个指向下一个节点的指针。要实现循环单链表的就地逆置，可以按照以下步骤操作。

1. 定义循环单链表的节点结构体，包含数据域和指向下一个节点的指针。

typedef struct node {
    int data;
    struct node *next;
} Node;

2. 定义循环单链表的头节点和当前节点。

Node *head = NULL;
Node *current = NULL;

3. 创建循环单链表，向链表中插入节点。

for (int i = 0; i < n; i++) {
    Node *newNode = malloc(sizeof(Node));
    newNode->data = data[i];
    newNode->next = NULL;
    if (head == NULL) {
        head = newNode;
        current = newNode;
    } else {
        current->next = newNode;
        current = newNode;
    }
}
current->next = head;

4. 遍历循环单链表，将链表就地逆置。

Node *prev = NULL;
Node *current = head;
Node *next = head->next;
while (current != head) {
    current->next = prev;
    prev = current;
    current = next;
    next = next->next;
}
current->next = prev;
head = prev;

完整的代码如下：

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

typedef struct node {
    int data;
    struct node *next;
} Node;

int main() {
    int n = 5;
    int data[] = {1, 2, 3, 4, 5};

    Node *head = NULL;
    Node *current = NULL;

    for (int i = 0; i < n; i++) {
        Node *newNode = malloc(sizeof(Node));
        newNode->data = data[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
            current = newNode;
        } else {
            current->next = newNode;
            current = newNode;
        }
    }
    current->next = head;

    Node *prev = NULL;
    Node *current = head;
    Node *next = head->next;
    while (current != head) {
        current->next = prev;
        prev = current;
        current = next;
        next = next->next;
    }
    current->next = prev;
    head = prev;

    printf("Reversed circular linked list: ");
    Node *temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    } while (temp != head);

    return 0;
}

输出结果为：

Reversed circular linked list: 5 4 3 2 1

用C语言编写一个高效算法，将一循环单链表就地逆置

在C语言中，可以使用迭代法来实现单链表的就地逆置，即不需要额外的空间，并直接操作原链表节点。这种方法的核心思想是通过三个指针prev、current和next来遍历链表并逐个交换节点的位置。

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

// 定义链表节点结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 就地逆置链表函数
void reverseList(Node** head) {
    if (*head == NULL || (*head)->next == NULL) { // 如果链表为空或只有一个元素，无需反转
        return;
    }
    
    Node* prev = NULL; // 初始化前驱节点为NULL
    Node* current = *head; // 当前节点指向头节点
    while (current != NULL) {
        Node* nextTemp = current->next; // 临时保存当前节点的下一个节点
        current->next = prev; // 更新当前节点的next指向前一个节点
        prev = current; // 移动前驱节点到当前节点
        current = nextTemp; // 移动当前节点到下一个节点
    }
    *head = prev; // 链表反转后，头节点变为原来的尾节点
}

// 打印链表帮助测试
void printList(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

int main() {
    // 创建示例链表
    Node* list = (Node*)malloc(sizeof(Node));
    list->data = 1;
    list->next = (Node*)malloc(sizeof(Node));
    list->next->data = 2;
    list->next->next = (Node*)malloc(sizeof(Node));
    list->next->next->data = 3;
    list->next->next->next = NULL;

    printf("Original List: ");
    printList(list);

    reverseList(&list); // 调用逆置函数

    printf("Reversed List: ");
    printList(list);

    return 0;
}