首页 > 代码库 > LeetCode:Swap Nodes in Pairs

LeetCode:Swap Nodes in Pairs

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.

思路:添加一个空的头指针,每两个结点一组,先链接后一个结点,再链接前一个结点(注意链接完后将该结点的next指针置为空)。

 

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *swapPairs(ListNode *head) {12         if(head==NULL||head->next==NULL)13             return head;14         ListNode *p=head,*q=p->next,*r;15         r->next=NULL;16         head=r;17         while(p!=NULL)18         {19             if(q!=NULL)20             {21                 head->next=q;22                 q=q->next;23                 head=head->next;24             }25             head->next=p;26             head=head->next;27             head->next=NULL;28             p=q;29             if(p!=NULL&&p->next!=NULL)30                 q=p->next;31         }32         return r->next;33     }34 };

 

LeetCode:Swap Nodes in Pairs