本文共 1248 字，大约阅读时间需要 4 分钟。

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

示例:

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

说明:

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

方法1：递归（写递归会被鄙视）

class Solution {public:    ListNode* swapPairs(ListNode* head) {        if(!head || !head->next) return head;        ListNode *p=head->next;        head->next=swapPairs(p->next);        p->next=head;        return p;    }};

方法2：循环，两个变量的

class Solution {public:    ListNode* swapPairs(ListNode* head) {        if(!head || !head->next) return head;        ListNode *dummy=new ListNode(0), *pre=dummy, *p=head;        dummy->next=head;        while(p && p->next){            pre->next=p->next;            swap(p->next->next,p);            pre=pre->next->next;            pre->next=p;        }        return dummy->next;    }};# 变量多，可读性更好class Solution {public:    ListNode* swapPairs(ListNode* head) {        while(head==nullptr || head->next==nullptr) return head;        ListNode *dummy=new ListNode(0), *pre=dummy, *p=head, *q=p->next;//head没用上，可以直接用head替代p，节省一个变量        dummy->next=head;        while(p && p->next){            pre->next=q;            p->next=q->next;            q->next=p;            pre=p;            p=p->next;//此时p有可能为空            if(p) q=p->next;        }        return dummy->next;    }};

转载地址：http://phabi.baihongyu.com/