题目链接

LeetCode

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

24. 两两交换链表中的节点 - 图1

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

示例 2：

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

示例 3：

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

提示：

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

进阶： 你能在不修改链表节点值的情况下解决这个问题吗?（也就是说，仅修改节点本身。）

解题思路

方法一：迭代修改

两两一组，迭代交换结点，进阶题目：K个一组反转链表

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* swapPairs(ListNode* head) {
  14.         if(head==nullptr||head->next==nullptr){
  15.             return head;
  16.         }
  17.         ListNode* hair = new ListNode();
  18.         hair->next = head;
  19.         // pre记录cur之前链表的指向，需要指向交换后的头节点
  20.         ListNode* pre = hair;
  21.         ListNode* cur = head;
  22.         while(cur&&cur->next){
  23.             ListNode* tmp = cur->next;
  24.             cur->next = cur->next->next;
  25.             tmp->next = cur;
  26.             // pre指向交换后的头节点，然后将pre前移到最后
  27.             pre->next = tmp;
  28.             pre = cur;
  29.             cur = cur->next;
  30.         }
  31.         return hair->next;
  32.     }
  33. };
  • 时间复杂度 O(n)
  • 空间复杂度 O(1)