题目

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.

解答

/** * 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){ return head; } ListNode *dummy=new ListNode(-1);//增加一个空的头结点 dummy->next=head; ListNode *p=dummy; ListNode *before=head; //表示交换的前一个元素 ListNode *after=head->next; //表示交换的后一个元素 while(after!=NULL&&before!=NULL){ //当链表中元素的个数为偶数时，before最终为NULL，after指向链表的最后一个元素，当元素的个数为奇数时，after为NULL，before指向链表的最后一个元素 ListNode *temp=after->next; //记录下次要进行交换第一个元素的位置 p->next=after; if(temp!=NULL) after=temp->next; p=p->next; p->next=before; before=temp; p=p->next; } if(before!=NULL){ //奇数个元素时，上面的交换未能够将最后一个元素插入到链表中 p->next=before; p=p->next; } p->next=NULL; return dummy->next; } };