两两交换链表中的节点

两两交换链表中的节点

方法一：递归

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

    ListNode* next = head->next;
    head->next = next->next;
    next->next = head;

    head = next;

    head->next->next = swapPairs(head->next->next);

    return head;
  }
};

解释:

1. 递归终止条件：当链表为空或只有一个节点时，直接返回。
2. 递归步骤：
   • 交换当前链表的第一个和第二个节点。
   • 将递归结果连接到交换后的第二个节点之后。
   • 返回交换后的第一个节点。

方法二：迭代

class Solution {
public:
  ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;

    ListNode* prev = dummy;
    while (head && head->next) {
      ListNode* next = head->next;
      head->next = next->next;
      next->next = head;

      prev->next = next;
      prev = head;
      head = head->next;
    }

    return dummy->next;
  }
};

解释:

1. 创建一个虚拟头节点 dummy，指向原链表的头节点。
2. 使用两个指针 prev 和 head 分别指向当前链表的前一个节点和当前节点。
3. 循环遍历链表，每次交换相邻的两个节点：
   • 将 head 的下一个节点赋值给 next。
   • 将 head 的下一个节点指向 next 的下一个节点。
   • 将 next 的下一个节点指向 head。
4. 将 prev 的下一个节点指向交换后的 next 节点。
5. 将 prev 指向 head。
6. 将 head 指向 head 的下一个节点。
7. 循环结束之后，返回 dummy 的下一个节点，即交换后的链表的头节点。

两种方法的复杂度分析:

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(1)

代码示例:

#include <iostream>

using namespace std;

struct ListNode {
  int val;
  ListNode* next;

  ListNode(int x) : val(x), next(nullptr) {}
};

void printList(ListNode* head) {
  while (head) {
    cout << head->val << " ";
    head = head->next;
  }
  cout << endl;
}

int main() {
  ListNode* head = new ListNode(1);
  head->next = new ListNode(2);
  head->next->next = new ListNode(3);
  head->next->next->next = new ListNode(4);

  Solution s;
  ListNode* newHead = s.swapPairs(head);

  printList(newHead);

  return 0;
}

输出：2 1 4 3