原题地址（中等）

方法1—迭代

思路

这题根本就不配中等难度，太水了，算简单题还差不多。

思路就是定义一个虚头结点，为了使操作归一化。然后就遍历链表，两两交换就可以了。

代码

  1. class Solution {
  2. public:
  3.     ListNode* swapPairs(ListNode* head) {
  4.         ListNode *empty_head = new ListNode(0);
  5.         empty_head->next = head;
  6.         ListNode *pre = empty_head, *p = head, *q = NULL;
  7.         if(head)  q = head->next;
  8.         while(p && q) {
  9.             // 交换
  10.             p->next = q->next;
  11.             pre->next = q;
  12.             q->next = p;
  13.             //后移指针
  14.             pre = p;
  15.             p = p->next;
  16.             if(p)   q = p->next;
  17.         }
  18.         return empty_head->next;
  19.     }
  20. };

时空复杂度

时间 O(n) 空间 O(1)

方法2—递归

思路

其实方法一最好，根本没必要用递归。
递归的话，只需要关注当前的两个点，函数返回值是除了当前两个点之外的链表，都交换好了之后的 头结点
所以就交换当前两个结点，然后让第二个结点的 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;
    }
};

时空复杂度

时间 O(n) 空间 O(n)