java - 如何使用递归在链表中成对交换节点？

Question

我正在尝试实现代码来交换链表中的两个相邻对，但在理解我的错误所在时遇到一些困难。

这是一个用 Java 编程语言实现的 leetcode 问题，我首先尝试了一种迭代解决方案，我分配了第一个初始节点和第三个初始节点，然后迭代所有节点，每 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