FMC_WBL的博客：LeetCode24. 两两交换链表中的节点

当前位置博文首页 > FMC_WBL的博客：LeetCode24. 两两交换链表中的节点

最大化缩小

FMC_WBL的博客：LeetCode24. 两两交换链表中的节点

作者：[db:作者] 时间：2021-08-28 18:46

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

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

输入：head = []
输出：[]
示例 3：

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

/**
 * @author mac
 * @date 2020/11/10-9:14
 */
public class t24_两两交换链表中的节点 {
    /**
     * 递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
     * 如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点， 原始链表的第二个节点变成新的链表的头节点。
     * 链表中的其余节点的两两交换可以递归地实现。
     * 在对链表中的其余节点递归地两两交换之后， 更新节点之间的指针关系，即可完成整个链表的两两交换。
     * <p>
     * 用 head 表示原始链表的头节点，新的链表的第二个节点,
     * 用 newHead 表示新的链表的头节点，原始链表的第二个节点，
     */
    public ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 则原始链表中的其余节点的头节点是 newHead.next
        ListNode newhead = head.next;

        // 令 head.next = swapPairs(newHead.next)，表示将其余节点进行两两交换,
        head.next = swapPairs1(newhead.next);

        // 交换后的新的头节点为 head 的下一个节点,然后令 newHead.next = head，即完成了所有节点的交换。
        newhead.next = head;

        // 最后返回新的链表的头节点 newHead
        return newhead;
    }

    /**
     * Definition for singly-linked list.
     */
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}

迭代法：图解在代码之后

/**
 * @author mac
 * @date 2020/11/10-9:14
 */
public class t24_两两交换链表中的节点 {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 创建一个链表前一个的节点，指向链表的头结点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 创建temp指针，用于迭代链表
        ListNode temp = dummyHead;

        // 遍历链表，如果temp的下一个和下下个为空，证明没有需要交换的节点
        while (temp.next != null && temp.next.next != null) {
            // 创建需要交换的两个指针
            // temp的下一个节点
            ListNode node1 = temp.next;
            // temp的下下个节点
            ListNode node2 = temp.next.next;

            // 步骤一： 将temp.next，指向node2（temp就指向node2了）
            temp.next = node2;

            // 步骤二： 将node1.next，指向node2.next（指向第四个了）
            node1.next = node2.next;

            // 步骤三： 将node2.next，指向node1（现在就变成 temp -> node2 -> node1 -> ***）
            node2.next = node1;

            // 步骤四： 将temp指针移动到node1上（node2 -> node1（temp） -> ***(再循环就是node1了) -> ***（node2） ）
            temp = node1;
        }

        // 最后返回新的链表的头节点dummyHead的下一个节点 head
        return dummyHead.next;
    }
}

第0步：