Swap Nodes in Pairs

LeetCode笔记 阅读(59)

编号 : 24      
难度 : <font color="orange">Medium</font>

# 题目 :  
>Given a linked list, swap every two adjacent nodes and return its head.
>
>You may **not** modify the values in the list's nodes, only nodes itself may be changed.
>
>**Example**:
>
>>Given 1->2->3->4, you should return the list as 2->1->4->3.
>

# 解 :  
```Cpp
/**
 * 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) {
        ListNode preHead(0);
        preHead.next = head;

        /* pos是要处理的两个节点中,靠前节点之前的节点 */
        ListNode* pos = &preHead;

        while(pos != nullptr && pos->next != nullptr && pos->next->next !=nullptr)
        {
            ListNode* left = pos->next;         // 靠前节点
            ListNode* right = pos->next->next;  // 靠后节点

            /* 靠前结点的next指向靠后节点的next */
            left->next = right->next;

            /* 靠后节点的next指向靠前节点 */
            right->next = left;

            /* pos->next指向后一个节点 */
            pos->next = right;

            /* 移动pos */
            pos = left;
        }

        return preHead.next;
    }
};
```

# 分析 :  
这道题要求将单向链表中的节点,两两互换(必须交换节点,而不能修改值),总的来说很简单,由于是单向链表,所以额外需要前一个节点。
```
pos -> left -> right -> N


pos -> left    right -> N
        |               ^
        +---------------+


        +--------+
        V        |
pos -> left    right    N
        |               ^
        +---------------+


 +-----------------+
 |      +------+   |
 |      V      |   V
pos    left    right    N
        |               ^
        +---------------+


pos -> right -> left -> N
```

Markdown使用 帮助