Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given1->2->3->4, you should return the list as2->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.
题意:成对交换结点。
思路:这题感觉是reverse nodes in k grops的是一个特殊情况。这题更简单一些,只要保证当前结点cur和其后继存在就可以交换。改变表头,所以要new一个。代码如下:
/**
* 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)
{
ListNode *nList=new ListNode(-);
nList->next=head;
ListNode *pre=nList;
ListNode *cur=head; while(cur&&cur->next)
{
ListNode *temp=cur->next;
cur->next=temp->next;
temp->next=pre->next;
pre->next=temp;
pre=cur;
cur=cur->next;
} return nList->next;
}
};