danh sách liên kết ngược lại không có temp

Question

Có cách nào để đảo ngược danh sách liên kết mà không sử dụng biến tạm thời trong C? Cảm ơn trước.

phương pháp nổi tiếng:

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

sử dụng biến temp

Saurabh

Answer 1

Lưu ý rằng việc sử dụng temp bạn đang thực sự tạo ra hai swap() cuộc gọi, và có thể được thay thế bằng:

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

Bạn có thể trao đổi mà không cần sử dụng temps xor, nó được gọi là xor swap.

Answer 2

Sử dụng XOR-swaps trên các con trỏ để giả mạo một XOR-linked-list.

thực hiện được để lại cho người đọc như một bài tập .

Answer 3

phương pháp đệ quy:

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

Gọi để biết hàm đệ quy:

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

Answer 4

Nếu ai đó vẫn còn quan tâm, đây là giải pháp mà không sử dụng các biến mới ở tất cả, trừ các đối tượng thông qua trong đệ quy gọi điện.

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

Ý tưởng là như sau: đầu tiên chúng ta chạy chức năng nghịch đệ quy, và thực hiện nó để khi nó đạt đến yếu tố cuối cùng nó gán nó như là một yếu tố tiếp theo của người đứng đầu hiện nay (tham số first). Sau khi chúng tôi thực hiện nó, chúng tôi sẽ có một danh sách đảo ngược nhưng đạp xe, do đó, head.next hiện tại sẽ trỏ vào phần đầu của danh sách đảo ngược. Chúng tôi gán lại đầu cho phần tử tiếp theo của nó (phần đầu thực sự của danh sách đảo ngược), và điều cuối cùng chúng ta phải làm là phá vỡ chu trình. Vì vậy, chúng tôi gọi breakCycle thực hiện công việc đệ quy!