обратный список связанных без температуры - PullRequest
Новая
       0

обратный список связанных без температуры

7 голосов
/ 12 января 2012

Есть ли способ перевернуть связанный список без использования временной переменной в 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;
}

использует переменную temp

Saurabh

Ответы [ 4 ]

6 голосов
/ 12 января 2012

Обратите внимание, что ваше использование temp фактически генерирует два swap() вызова и может быть заменено на: 

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

Вы можете поменяться без временных переменных с помощью xor, это называется xor swap.

3 голосов
/ 12 января 2012

Используйте XOR-swaps на указателях, чтобы подделать XOR-связанный список.

Реализация оставлена ​​читателю в качестве упражнения.

1 голос
/ 05 июня 2012

Рекурсивный подход: 

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);
0 голосов
/ 30 ноября 2014

Если кому-то все еще интересно, вот решение, которое вообще не использует никаких новых переменных, кроме тех, которые передаются в рекурсивном вызове. 

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, который выполняет работу рекурсивно!

...