Link to LeetCode Problem

S1: 迭代

简单的链表指针操作题，注意穿针引线的时候别打结了。

• 注意指针改变的顺序，不然可能会丢失节点，不熟悉可以画图，或者先用变量把指针存起来，写得啰嗦点。
• 可以加一个 dummy 节点在 head 前，简化操作，免去对头部节点的额外操作，是链表题目的常用技巧。

https://camo.githubusercontent.com/b66080a8fd804e7ed7002a1ff561cd6042c5e5885ea17e0346ec559f9e747a3d/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f30372e737761702d6e6f6465732d696e2d70616972732d30322e706e67

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        // 使用一个 dummy 节点来简化操作
        // 不用额外处理头部节点，把头部节点也当成链表中间的一个节点处理即可
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = dummy;
        ListNode* cur = head;

        // 存在一对节点的时候才进行两两交换
        while (cur != nullptr && cur->next != nullptr) {
            ListNode* first = cur;
            ListNode* second = cur->next;
            first->next = second->next;
            second->next = first;

            prev->next = second;
            prev = first;
            cur = first->next;
        }
        return dummy->next;
    }
};

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function (head) {
  const dummy = new ListNode(null, head);
  let prev = dummy;
  let cur = prev.next;

  while (cur && cur.next) {
    // 按照上图，指针更换顺序是这样子的
    // prev.next = cur.next
    // cur.next = prev.next.next
    // prev.next.next = cur

    // 也可以先用一个指针把下一个节点存起来
    const next = cur.next;
    cur.next = next.next;
    next.next = cur;
    prev.next = next;

    prev = cur;
    cur = cur.next;
  }
  return dummy.next;
};

• Time: $O(N)$，N 是链表的长度。
• Space: $O(1)$

S2: 递归

用递归来解决这个问题时，我们只需要考虑这几个问题：

小问题

当前递归函数需要解决什么问题？将前后的情况都当作黑匣子，我们只需要关注当前的递归函数即可，答案显然是将两个节点进行交换

https://camo.githubusercontent.com/d3a748ec184d989953abca98977a1b4eae07f3e250b40ab0714e9b259f77da9f/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f30372e737761702d6e6f6465732d696e2d70616972732d30302e706e67

小问题之间的关系

我们将链表进行两两分组，在每个递归函数中只处理一组节点，那么各个递归函数之间的关系是什么？答案也是显而易见的，需要将各组节点重新连接。再具体点就是，下一层递归函数需要返回什么数据给当前函数，而当前递归函数需要什么数据给上一层递归函数，这两个其实是一个问题。就这道问题而已，需要返回的是交换后的第一个节点。

https://camo.githubusercontent.com/1bfc5fa8f248c28b9f725b706fdcaf557ab1082328d27c8924d11ab02dc8b45b/68747470733a2f2f63646e2e6a7364656c6976722e6e65742f67682f7375756b69692f39312d646179732d616c676f726974686d2f6173736574732f30372e737761702d6e6f6465732d696e2d70616972732d30312e706e67

递归出口