题目描述

　　给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

　　你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

　　示例:

　　给定 1->2->3->4. 你应该返回 2->1->4->3.

　　题目解析

　　该题属于基本的链表操作题。

　　设置一个虚拟头结点dummyHead

　　设置需要交换的两个节点分别为node1、node2.同时设置node2的下一个节点next

　　在这一轮操作中

　　将node2节点的next设置为node1节点

　　将node1节点的next设置为next节点

　　将dummyHead节点的next设置为node2

　　结束本轮操作

　　接下来的每轮操作都按照上述进行。

　　代码实现

　　// 时间复杂度: O(n)

　　// 空间复杂度: O(1)

　　class Solution {

　　public:

　　ListNode* swapPairs(ListNode* head) {

　　ListNode* dummyHead = new ListNode(0);

　　dummyHead->next = head;

　　ListNode* p = dummyHead;

　　while(p->next && p->next->next){

　　ListNode* node1 = p->next;

　　ListNode* node2 = node1->next;

　　ListNode* next = node2->next;

　　node2->next = node1;

　　node1->next = next;

　　p->next = node2;

　　p = node1;

　　}

　　ListNode* retHead = dummyHead->next;

　　delete dummyHead;

　　return retHead;

　　}

　　};

上一篇

大数据之三数之和

下一篇

大数据之最长回文串