Day78 | 灵神 | 反转链表 两两交换链表中的节点

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

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

思路：

这道题就是下面这道题的k==2的情况

25. K 个一组翻转链表 - 力扣（LeetCode）

基本思路和92. 反转链表 II - 力扣（LeetCode）一样

用第一个例子[1,2,3,4,5]作为说明，就是说，步骤为

1.建立虚拟头结点t，作为要反转部分[1,2]的前一个节点，以后每反转一部分都要更新和保存反转部分的前一个节点

2.再次建立一个临时节点q保存要反转部分的后一个结点[3]

3.建立两个指针指向要交换的两个节点，cur指向2，pre指向1

4.反转指针把2指向1

5.把反转部分接到原来链表上

  • 5.1 [1]的next即pre的next指向[3]，即q，这是把后面接好了
  • 5.2 虚拟头结点t的next指向[2]，即cur，这是把前面接好了

6.更新并保存t，把t更新为1，即pre，因为pre是下一段要反转部分[3,4]的前一个节点

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //1.建立虚拟头结点
        ListNode * t=new ListNode;
        t->next=head;
        ListNode * res=t;
        while(t&&t->next&&t->next->next)
        {
            //2,3步
            ListNode *pre=t->next;
            ListNode *cur=pre->next;
            ListNode *q=cur->next;
            //4
            cur->next=pre;
            //5.
            pre->next=q;
            t->next=cur;
            //6.
            t=t->next->next;
        }
        return res->next;
    }
};