Leetcode 24. 两两交换链表中的节点(Swap nodes in pairs)

Ahci / 2023-08-31 / 原文

题目链接

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1:

输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2:

输入：head = []
输出：[]

示例 3:

输入：head = [1]
输出：[1]

提示:

链表中节点的数目在范围 [0, 100] 内
0 <= Node.val <= 100

思路

迭代法

这道题两种解法, 先说比较简单的迭代法, 这种链表题目最好都建立一个虚拟头节点(dummy), 这样可以让头节点的操作和其他节点一样, 而不用为头节点单设计一种方法.

使用临时节点(current)指向dummy, 进入循环, 因为要交换的节点不包括虚拟节点, 所以循环条件应该是current.next != null || current.next.next != null

接下来在循环中交换current.next和current.next.next的位置即可. 需要注意的是在最后记得让current前进, 不然就变成死循环了.

递归

第二种方法是递归, 递归我一直不太会, 不过这道题的递归比较简单(在看了题解后).

思路是每次递归交换两个节点, 所以递归结束条件应该是head != null && head.next != null 若满足结束条件, 直接返回head(链表个数是单数时返回的是不用交换的那个节点, 链表个数是双数时返回的是null)

进入递归, head是第一个节点, newHead是第二个节点. 每次递归只交换这俩节点, 交换后newHead在前, head在后, 所以head.next = swapPairs(newHead.next); (也就是指向下一次递归后位置在前的节点)

然后使newHead.next = head, 就完成了交换. 最后返回新的链表头节点newHead即可.

大家难以理解可以画图模拟一下.

代码实现

迭代法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode current = dummy;

        while(current.next != null && current.next.next != null) {
            ListNode firstNode = current.next;
            ListNode secondNode = current.next.next;

            current.next = secondNode;
            firstNode.next = secondNode.next;
            secondNode.next = firstNode;
            current = firstNode;
        }

        return dummy.next;
    }
}

递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}