Swap Nodes in Pairs
LeetCode笔记 阅读(415)
编号 : 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 ```