我们可以仅使用两个指针来反转单循环链表中的元素吗？可行、高效，但时间复杂度如何？

Question

我只需要清楚地了解一件事，因为我已经尝试过使用C语言实现单循环链表反转。因为我找不到正确的方法，而且我对此一无所知。有人可以帮助我以正确的方式并简要说明时间复杂度，最后我们不能在不声明 NULL 的情况下逆转吗？

struct node *Reversescll(struct node *head) {
    if (head == NULL) {
        head->next = head;
        return head;
    }

    struct node *back = NULL;
    struct node *c = head;
    struct node *next = NULL;

    do {
        next = c->next;
        c->next = back;
        back = c;
        c = next;
    } while (c != head);

    head->next = back;
    head = back;
    return head;
}

Answer 1

您的方法几乎是正确的，但是空列表有问题：您应该只返回

head

或

NULL

，而不是当

head->next

为

head

时取消引用

NULL

。

这是更正后的版本：

struct node *Reversescll(struct node *head) {
    if (head == NULL || head->next == head)
        return head;

    struct node *back = NULL;
    struct node *c = head;

    do {
        struct node *next = c->next;
        c->next = back;
        back = c;
        c = next;
    } while (c != head);

    head->next = back;
    return head;
}

请注意，该函数始终返回其参数。