链接列表反向没有临时

有没有什么办法可以反转链接列表，而不使用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

来源

2012-01-11 Saurabh Ghorpade

如何递归呢？ – 2012-01-11 22:24:46

递归是一种骗局，因为参数本质上是临时变量。 – 2012-01-11 22:35:50

同意，但这通常是像这个一样的语义呃问题。 – 2012-01-11 22:37:12

请注意，您的temp的使用实际上是产生两个swap()通话，并且可以替换为：

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

您可以在不使用XOR临时工交换，它被称为xor swap。

来源

2012-01-11 22:29:47 amit

使用XOR-swaps上的指针假的XOR-linked-list.

实现留给读者作为一个练习。

来源

2012-01-11 22:25:04

递归方法：

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

来源

2012-06-05 13:30:07 Sach

如果有人仍然有兴趣，这里是不使用新的变量可言，除了那些在递归传递的解决方案呼叫。

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

的想法是这样的：第一，我们运行反向功能递归，并执行它，这样，当它达到其分配为当期头的下一个元素的最后一个元素（参数first）。在我们执行它之后，我们将有一个反转列表，但循环，所以当前head.next将指向反转列表的头部。我们重新分配下一个元素（反向列表的实际首长），我们最后要做的就是打破这个循环。所以我们称之为breakCycle这是递归的工作！

来源

2014-11-30 12:25:54 heorhi

链接列表反向没有临时

回答

相关问题