c-链表反向不带临时

Question

有没有任何方法可以在不使用C中的临时变量的情况下反转链表？提前谢谢。

著名的方法：

Element *reverse(Element *head)
{
    Element *previous = NULL;
    while (head != NULL) {
        // Keep next node since we trash
        // the next pointer.
        Element *next = head->next;
        // Switch the next pointer
        // to point backwards.
        head->next = previous;
        // Move both pointers forward.
        previous = head;
        head = next;
    }
    return previous;
}

使用温度变量

Saurabh

Answer 1

请注意，您的temp使用实际上生成了两个swap()调用，并且可以替换为：

swap(head->next,previous);
swap(previous,head);

您可以使用xor在没有temps的情况下进行交换，这被称为xor交换。

Answer 2

在指针上使用XOR交换来伪造XOR链表。

实现留给读者作为练习

Answer 3

递归方法：

Element *reverse(Element *head, Element **first)
{
    if (head->next == NULL)
    {
        *first = head;
        return head;
    }

     Element* NextElement= reverse  (head->next, first);
     NextElement->next = head;
     head->next = null;
     return head;
}

调用递归函数：

   Element *revLinkListHead;
   reverse(head, &revLinkListHead);

Answer 4

如果有人仍然感兴趣，这里的解决方案根本不使用新变量，除了递归调用中传递的变量。

public static List invert(List l) {
    invert(l.next, l, l);
    l = l.next;
    breakCycle(l, l);
    return l;
}
private static void invert(List l, List toBeNext, List first) {
    if(l.next == null) {
        l.next = toBeNext;
        first.next = l;
    } else {
        invert(l.next, l, first);
        l.next = toBeNext;
    }
}
private static void breakCycle(List l, List first) {
    if(l.next == first) {
        l.next = null;
    } else {
        breakCycle(l.next, first);
    }
}

其思想如下：首先，我们递归地运行inverse函数，并实现它，以便当它到达最后一个元素时，它将其指定为当前头的下一个元素（参数first）。在我们执行它之后，我们将有一个反向列表，但它是循环的，所以当前的head.next将指向反向列表的头。我们将head重新分配给它的下一个元素（反向列表的实际head），最后要做的就是打破这个循环。所以我们调用breakCycle，它递归地完成任务！