Как использовать рекурсию для замены узлов в парах в связанном списке?

Question

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

Это для проблемы кода leetcode, реализованной с языком программирования Java. Сначала я попробовал итеративное решение, в котором я выделил первый начальный узел и третий начальный узел, а затем итерацию всех узлов, переключающихся каждые 2. Моя вторая попытка рекурсивное решение с проверкой базового случая на наличие 0 или 1 узла. Затем я поменял местами первые 2 узла, затем прошел через остальную часть связанного списка, а затем присоединился к связанному списку.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
public ListNode swapPairs(ListNode head) {

    if(head == null || (head.next == null)){return head;}
    //first we swap the first node and the second node
    ListNode first = head;
    ListNode third = head.next.next;
    first.next.next = first;
    first.next = third;



    //then we recurse on part of the linked list

    ListNode recursedList = swapPairs(head.next.next);

    //we join these two linked lists together
    first.next.next = recursedList;


    //and finally we return the head

    return head;
}
}

Для образца ввода
[1,2,3,4] решение [2,1,4,3] но мое решение дает [1,3,4]. Где в моем коде моя логика ошибочна?

Answer 1

Поверьте, это просто простая ошибка.

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

    # swapping the first and second
    ListNode second = new ListNode(head.val);
    ListNode first = new ListNode(head.next.val);
    first.next = second;

    # recursively swap the next 2 items in the linked list till the end of list
    ListNode recursedList = swapPairs(head.next.next);

    first.next.next = recursedList;

    return first;
}

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

Основная ошибка заключается в том, что вы меняли первый узел и третий узел, а не первый и второй (не соседние пары). Кроме того, такие назначения, как ListNode first = head;, делают только мелкие копии. Это означает, что если вы попробуете следующее ...

printLinkedList(head); # function to print out the entire linked list
ListNode first = head;
first.val = 100;
first.next = head.next.next.next;
printLinkedList(head);

... вы обнаружите, что изменение first также изменило head , и вы получите следующие результаты печати:

1 -> 2 -> 3 -> 4 -> null
100 -> 4 -> null