单循环链表反转技术咨询：双指针可行性、复杂度及无NULL实现

一、核心问题解答 #

• 能否仅用两个指针反转？ 可行。实际实现中会用到一个临时指针存下一个节点，但核心逻辑只依赖两个遍历指针（prev和curr），属于O(1)空间的高效解法。
• 效率与时间复杂度：时间复杂度是O(n)，n为链表节点数——必须遍历每个节点一次，每个节点的指针调整都是常数时间操作；空间复杂度O(1)，仅用固定数量的指针变量，没有额外内存开销。
• 能否不借助NULL反转？ 可以，完全不需要依赖NULL，利用链表自身的循环特性就能实现。

二、你的代码问题分析 #

你提供的代码存在两处关键问题：

1. 空链表处理逻辑错误：当head == NULL时，直接访问head->next会触发空指针异常，空指针没有成员可访问。
2. 依赖NULL的同时，最后恢复循环的逻辑虽然能跑，但不符合“不借助NULL”的需求，且空链表和单节点链表的边界处理不全。

三、正确实现代码 #

版本1：借助NULL的修正版 #

在你原有代码基础上修复边界问题，逻辑更严谨：

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

struct node *ReverseScll(struct node *head) {
    // 空链表或只有一个节点，直接返回原头
    if (head == NULL || head->next == head) {
        return head;
    }

    struct node *prev = NULL;
    struct node *curr = head;
    struct node *nextNode;

    do {
        nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    } while (curr != head);

    // 把原头节点的next指向新头，恢复循环
    head->next = prev;
    // 更新头节点为反转后的第一个节点
    head = prev;
    return head;
}

版本2：不借助NULL的纯循环反转版 #

全程不使用NULL，完全依托链表的循环特性：

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

    struct node *prev = head;
    struct node *curr = head->next;
    struct node *nextNode;

    // 遍历所有节点，逐个反转指针
    while (curr != head) {
        nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }

    // 原头节点的next指向反转后的最后一个节点（即新头）
    head->next = prev;
    head = prev;
    return head;
}

四、关键逻辑说明 #

• 两个版本的时间复杂度都是O(n)，因为必须遍历每个节点一次，没有冗余操作。
• 不借助NULL的版本，初始时让prev指向原头节点，curr从第二个节点开始，每次把curr的next指向prev，逐步推进到原头节点时停止，最后调整原头的next指向prev（此时prev是原链表的最后一个节点，反转后成为新头），整个链表依然保持循环状态。

内容的提问来源于stack exchange，提问作者SRIRAM M