24. 两两交换链表中的节点

24. 两两交换链表中的节点 - 力扣（LeetCode）

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    if (!head)
      return nullptr;

    ListNode *Odd = head;
    ListNode *Even = head->next;
    ListNode *EvenPre = nullptr;
    while (Even) {
      if (head == Odd)
        head = Even;

      ListNode *OddNext = Even->next;

      Even->next = Odd;
      Odd->next = OddNext;

      if (EvenPre)
        EvenPre->next = Even;

      EvenPre = Odd;
      Odd = OddNext;

      if (!Odd)
        break;

      Even = Odd->next;
    }

    return head;
  }
};

这种题目用迭代方法解的话就画图、多设几个节点，然后把变量名搞搞清楚，再用分支语句处理处理边界条件就可以了，有通解的。

不过说实话这个递归解法确实是可以，我一开始其实也在想要不要从整个链表的最后开始做这个操作，结果没意识到递归天然就是倒序的，这一点着实有趣。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};

二刷

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next)
      return head;
    ListNode *NewHead = head->next;
    ListNode *Tail = head->next->next;
    NewHead->next = head;
    head->next = swapPairs(Tail);
    return NewHead;
  }
};

我这还设了个 Tail，其实也不用这么麻烦，调整一下递归语句所在的位置就可以避免多设置一个变量了。

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    if (!head || !head->next)
      return head;
    ListNode *NewHead = head->next;
    head->next = swapPairs(NewHead->next);
    NewHead->next = head;
    return NewHead;
  }
};

迭代方法也试着写了一下。

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    ListNode Dummy(0, head);
    ListNode *This = head, *Prev = &Dummy;
    while (This && This->next) {
      ListNode *Next = This->next->next;
      This->next->next = This;
      Prev->next = This->next;
      This->next = Next;
      Prev = This;
      This = Next;
    }
    return Dummy.next;
  }
};

我发现迭代到处都是这个 Dummy，还有这个 Prev = &Dummy。看起来迭代就该这么写。

三刷

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    ListNode Header(0, head), *Prev = &Header;
    ListNode *Curr = head;
    while (Curr && Curr->next) {
      ListNode *Next = Curr->next->next;
      Prev->next = Curr->next;
      Curr->next->next = Curr;
      // Although this might seem not required, it's actually useful when the
      // tail needs not to be swapped, i.e. Curr && Curr->next is false.
      Curr->next = Next;
      Prev = Curr;
      Curr = Next;
    }
    return Header.next;
  }
};

这里的 Curr->next = Next; 是必要的。实际上按照直觉来看，只有 Prev->next = Curr->next; 是必要的，因为每个子链表反转后头都会发生变化，所以需要将 Prev->next 连接到新头上——但是注意了，如果我们不对 Curr->next 进行提前赋值，我们就会遇到一个重复引用的情况，导致发生 heap use after free。

如图，上面的操作是错误的，而下面的才是正确的。

三刷

class Solution {
  ListNode *Reverse(ListNode *LN) {
    ListNode *Prev = nullptr;
    ListNode *Cur = LN;
    while (Cur) {
      ListNode *Next = Cur->next;
      Cur->next = Prev;
      Prev = Cur;
      Cur = Next;
    } // else
    // return Cur;
    return Prev;
  }

public:
  ListNode* swapPairs(ListNode* head) {
    if (!head)
      return nullptr;
    ListNode Pre(0, head), *Prev = &Pre;

    while (head && head->next) {
      ListNode *Next = head->next->next;
      head->next->next = nullptr;
      Prev->next = Reverse(head);
      Prev = head;
      head = Next;
    }
    Prev->next = head;
    return Pre.next;
  }
};

绷，一开始把return Prev;写成return Cur;了，怪不得结果里什么都没有。下次debug真得在每个while后面都写个else。