原题网址：

描述

给一个链表，两两交换其中的节点，然后返回交换后的链表。

您在真实的面试中是否遇到过这个题？  是

样例

给出 1->2->3->4, 你应该返回的链表是 2->1->4->3。

挑战

你的算法只能使用常数的额外空间，并且不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

标签

链表

 

 

 

思路：要形成一个新链表，主要操作就是挂载节点，应该搞清楚在哪个节点上挂载哪个节点。

 

为操作方便，可以定义一个象征头结点，则当前等待被挂载节点的前驱节点pre的初始值可以设置为象征头结点。

 

遍历原链表，如果当前节点及当前节点的后继节点都不为NULL时：

1.将当前节点的后继节点的后继节点用一个临时变量保存起来；

2.将当前节点的后继节点挂载到前驱节点pre上；

3.将当前节点的后继节点的next值设置为当前节点，即完成相邻两个节点交换操作；

4.注意！为防止两个节点互相挂载形成闭环，需要将尾部的节点也就是交换后的当前节点next值赋为NULL；

5.更新前驱节点，更新后pre应为位于新链表尾部的当前节点；

6.用临时变量更新当前节点；

 

注意链表节点数为奇数的情况，即循环结束后，若当前节点不为NULL，说明原链表还剩下一个尾节点需要挂载到新链表上。

 

AC代码：

/** * Definition of singly-linked-list: * class ListNode { * public: *     int val; *     ListNode *next; *     ListNode(int val) { *        this->val = val; *        this->next = NULL; *     } * } */class Solution {public:    /**     * @param head: a ListNode     * @return: a ListNode     */    ListNode * swapPairs(ListNode * head) {        // write your code here    if (head==NULL)    {        return head;    }    ListNode *tmp=NULL;    ListNode * newhead=new ListNode(0);    ListNode *pre=newhead;//被挂载的前驱节点;    while(head!=NULL&&head->next!=NULL)    {        tmp=head->next->next;//保存后续节点地址;        //交换;        pre->next=head->next;        head->next->next=head;        head->next=NULL; //防止出现闭环;        pre=head;        head=tmp;    }    if (head!=NULL)//若链表节点个数为奇数，将最后一个节点挂载上去;    {        pre->next=head;    }    return newhead->next;    }};

 

 其他思路：

 

 非挑战版：   这个思路比较直观，就是直接交换两个节点的数据。