Swap List Node

发表于 | 分类于

Swap List Node

题目描述：

给定链表的头节点，交换链表中两两链表节点。

例子：

具体描述可以看LeetCode24

解题思路：

解题的思路很直接，我们直接交换节点即可。主要需要注意的是：我们需要用到虚拟头节点的技巧便于处理链表头部；改变链表指向的时候需要注意顺序；到达链表尾部的判断。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return head;
        //空节点直接返回
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        //定义虚拟头结点指向链表头部
        ListNode* first = dummy;
        ListNode* second = first->next;
        ListNode* third = second->next;
        //定义三个节点的初始位置
        while(second && third){
            ListNode* next = third->next;
            //保存下一个节点
            third->next = second;
            //第二个节点指向改变
            second->next = next;
            //第一个节点指向改变
            first->next = third;
            // 重连交换后节点
            first = second;
            second = next;
            third = !second ? NULL : second->next;
            //节点往下移动用于遍历
        }
        return dummy->next;
    }
};