reverse - 如何反转循环单链表

Question

反转单个链表很容易，下面的代码可以正常工作。

void reverse_list (SLINK list)
{
    SLINK tmp = list->next; 
    NODE *cur = NULL;
    list->next = NULL;
    for (; NULL != tmp;)    
    {
            cur = tmp;
            tmp = tmp->next;
            cur->next = list->next;
            list->next = cur;
    }
}

如何反转循环单链表？我将代码调整为此

SLINK reverse_list (SLINK rear)
{
    NODE *tag = rear->next;
    SLINK tmp = rear->next;
    NODE *cur = NULL;
    rear->next = NULL;
    for (; NULL != tmp; )
    {
        cur = tmp;
        tmp = tmp->next;
        cur->next = rear;
        rear->next = cur;
    }
    rear = tag;
    return rear;
}

但它不起作用，我以为运行这个函数后，循环列表将是非循环的，实际上，转储它后，我发现它仍然是一个循环列表。一定是我逻辑错了，请指正。

Answer 1

像 Amit 一样，我不太了解您的代码背后的想法......但从纯粹逻辑的角度来看，如果您已经知道如何翻转常规列表，那么您最好的选择是复制您的所有元素将循环列表转换为带有“for”的新常规列表，当第一个元素等于当前元素时停止，然后使用您的代码翻转新列表以反转单链表。

Answer 2

不知道为什么你说反转单链表的代码就可以了。在我看来，它看起来不对。行 cur->next = list->next; 鉴于您已经在循环外将 list->next 设置为 NULL，它不会将第二个节点的 next 指针设置为 NULL 吗？它不应该去第一个节点吗？

为什么你期望循环链表的反转会导致线性链表？如果您要在一张纸上绘制圆形列表，则反转只会导致链接方向顺时针到逆时针（反之亦然）偏移。

循环列表反向和线性列表反向之间的唯一逻辑变化是，在循环链表的情况下，您不会将第一个节点的下一个指针设置为 NULL

Answer 3

这是一种方法；

node *toggle(node *start){

        node *p=NULL;
        node *c=start;
        node *ne=NULL;
        node *e;
        int f=0;
        do{
            ne=c->next;
            c->next=p;
            p=c;
            if(f==0){
                e=p;
                f=1;
            }
            c=ne;
        }while(c!=start);

        start=p;
        e->next=p;
return start;

}