Swap Nodes in Pairs

LeetCode笔记 阅读(288)

编号 : 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使用 帮助


匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

富强 民主 文明 和谐 自由 平等 公正 法治 爱国 敬业 诚信 友善

匿名

我有一头小毛驴,我从来也不骑。