Узлы подкачки в парах в однонаправленного списка


Описание:

Дан связный список, поменять местами каждые два соседних узлов и возвращает его голову.

Например, учитывая 1->2->3->4, Вы должны вернуть список 2->1->4->3.

Ваш алгоритм должен использовать только постоянные места. Вы не можете изменять значения в списке, только узлы сам может быть изменено.

Код:

class Solution {
    public ListNode swapPairs(ListNode head) {

        if (head == null || head.next == null) {
            return head;
        }

        ListNode current = head;
        ListNode prev = null;
        ListNode newHead = head.next;

        while (current != null && current.next != null) {

            ListNode first  = current;
            ListNode second = current.next;

            first.next = second.next;
            second.next = first;

            // check if its not the first pair
            if (prev != null) {
                prev.next = second;
            }

            // update pointers
            current = second;
            prev = current.next;
            current = current.next.next;
        }
        return newHead;
    }
}

Вопросы:

Приведенный выше код проходит все тесты, основная борьба была замена логику и только после того, как я выбрал значимые имена first и second Я был в состоянии очистить свои мысли и двигаться вперед. Снова я вижу, что связанный список включает в себя много пограничных случаев, специально управляющий указатели.

Я хотел бы знать, если есть некоторые хорошо знать точки, чтобы избежать распространенных ошибок в связанные списки.

PS: Другие отзывы приветствуются



Комментарии
2 ответа

Опять же, разделять это на разные части пойдет на пользу решение. В основном:


  • Метод, который меняет местами первые два элемента в данный список, если имеются хотя бы два элемента. Затем вернуться новый первый элемент. (Просто вернуть один элемент, если он существует.)

  • Метод, который перебирает: назвать первый метод в списке голове, затем вперед дважды текущего указателя, а затем снова вызвать метод обновления и следующий указатель текущего узла. Повторяйте, пока не закончил.

В общем: всегда пытайтесь разбить проблему на части, которые можно решать отдельно.


Из-за комментариев ниже, я считаю своим долгом разбить мое личное правило, не просто разместив код. Таким образом, здесь работает (не глубоко тестирование) - подход, который использует идеи, представленные выше. Я надеюсь, что делает его более четким. (Примечание: зисс == преемника, что это имена я узнал в школе давным-давно...)

private static <T> ListNode<T> pairSwapHead(ListNode<T> head) {
if(head == null || head.succ == null)
return head;
ListNode<T> next = head.succ;
head.succ = next.succ;
next.succ = head;
return next;
}

private static <T> ListNode<T> pairSwapList(ListNode<T> head) {
ListNode<T> curr = pairSwapHead(head);
ListNode<T> res = curr; // result of first swap is new head == return value

while(curr != null && curr.succ != null) {
// second node of the current pair, which needs the next pointer
// adjusted after the sublist starting at offset 2 gets swapped
ListNode<T> needsNewNext = curr.succ;
curr = curr.succ.succ; // advance to sublist at offset two
curr = pairSwapHead(curr); // swap first two elements
needsNewNext.succ = curr; // and adjust the pointer
}
return res;
}

1
ответ дан 9 апреля 2018 в 08:04 Источник Поделиться

Общий алгоритм "" уже выглядит довольно прилично. Единственная небольшая проблема-это, как вы сами отметили, что вы создаете дополнительные переменные, чтобы просто дать им разные имена.

Если вы перепрофилировать его немного я думаю, что это достаточно читабельна без них.

Это помогает, если вы начинаете с обновлением "предыдущий" в начале цикла. Я имею в виду и установка prev.next к current.next а потом обновление prev стоимости, что станет новым вторым ListNode. Таким образом, мы знаем, что часть полностью обработаны и нам не нужно держать мысленную заметку не исправить.

После этого Вам только нужно поменять 2 узлы и установки current для следующей итерации. Когда я переписал этот мой язь начал жаловаться, что current переменная является избыточным, а также. Вы можете просто использовать входной параметр для этого.

Результат выглядит так:

public static ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}

ListNode result = head.next;

ListNode prev = null;
while (head != null && head.next != null) {
if (prev != null) {
prev.next = head.next;
}
//head will become the first after swap
prev = head;

//the actual swap
ListNode temp = head.next;
head.next = temp.next;
temp.next = head;

//head is the second one after the swap. Take the next of that one for the new head in the next iteration
head = head.next;
}

return result;
}

Я бы переименовал newHead для result чтобы сделать его еще более очевидно, что это то, что мы вернемся в конце метода. Вы действительно не нужно этого делать.

Я ставлю в комментарии, чтобы помочь вам читать код. Обычно я не стал бы включать в производственном коде.


Бонус: есть способ повторно использовать prev переменная вместо создания нового temp. Это весело, чтобы сделать, если вы никогда не хочу, чтобы тебя кто-то понял ваш код. Пожалуйста, не оптимизировать, как это в реальное производство код:

public static ListNode swapPairs(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode result = head.next;
ListNode temp = null;
while (head != null && head.next != null) {
if (temp != null) {
temp.next = head.next;
}
temp = head;
head = head.next;

temp.next = head.next;
head.next = temp;

head = temp.next;
}
return result;
}

1
ответ дан 9 апреля 2018 в 02:04 Источник Поделиться