题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解

解法一 迭代模拟法

手写模拟了一下两两交换的逻辑，发现使用四个标记指针来进行交换变链操作，比较容易理解

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        // 需要用到四个标记指针来模拟
        ListNode node0 = null, node1, node2, node3 = head, result = head.next; 
        while (node3 != null && node3.next != null) {
            // 移动指针
            node1 = node3;
            node2 = node3.next;
            node3 = node3.next.next;
            // 交换
            if (node0 != null){
                node0.next = node2;
            }
            node0 = node1;
            node2.next = node1;
            node1.next = node3;  
        }
        return result;
    }
}

解法二 递归解法

上面的解法每次操作都是重复的逻辑

因为每次交换后的后面的节点的后面的节点要在后面一对交换后才知道，所以可以让后面的函数返回交换后的前置元素。

像这样的逻辑可以用递归来优雅的实现：

class Solution {
    public ListNode swapPairs(ListNode head) {
        // 每次递归交换head的两个元素
        if (head == null || head.next == null) return head;
        ListNode newHead = head.next;
        head.next = swapPairs(newHead.next);
        newHead.next = head;
        return newHead;
    }
}

小结

今天实际上做了两道题，第一题是19. 删除链表的倒数第N个结点，用到了快慢指针的技巧，在一轮循环中找到倒数第N个结点，执行删除操作。

链表类的题大多可以通过维护较多的标记指针来实现原链表上的操作。而且很多都是用while循环重复组操作，这样的代码可以用递归的思想来更优雅的实现，以后要尽量留意题目的递归实现，写出更优雅的代码！