不带温度的链表反向

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 在没有临时值的情况下进行交换，称为 异或交换。

Answer 2

在指针上使用XOR-swaps来伪造XOR-linked-list。

实现留给读者作为练习。

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);
    }
}

这个想法如下：首先我们递归地运行 invert 函数，并实现它，以便当它到达最后一个元素时，它将它分配为当前头的下一个元素（参数 first）。执行后，我们将得到一个反向列表，但会循环，因此当前的 head.next 将指向反向列表的头部。我们将 head 重新分配给它的下一个元素（反向列表的实际头），我们要做的最后一件事就是打破循环。所以我们调用 breakCycle 来递归地完成这项工作！