Swap Nodes in Pairs

时间：2014-03-06 08:31:30 阅读：373 评论：0 收藏：0 [点我收藏+]

Given a linked list, swap every two adjacent nodes and return its head.

For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

1. 用一个dummy node表示head的前一个节点；
2. 保证至少有两个node是有效的（node2, node3)，同时保有pre和next指针（可以认为是node1，node4）
3.交换node2和node3，更新pre的next指针，
4. 更新pre，同时获得下两天node的指针（如果都存在，不然就退出）

-------------------------
/**
* 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 == NULL || head->next == NULL) return head;
ListNode dummy(-1);
dummy.next = head;
ListNode *pre = &dummy;
ListNode *cur = head;
while (cur != NULL && cur->next != NULL) {
ListNode *p2 = cur->next;
ListNode *next = p2->next;
cur->next = next;
p2->next = cur;
pre->next = p2;
pre = cur;
cur = next;
}

return dummy.next;
}
};

Swap Nodes in Pairs,布布扣,bubuko.com

Swap Nodes in Pairs

原文：http://blog.csdn.net/icomputational/article/details/20577227

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)