给一个链表,两两交换其中的节点,然后返回交换后的链表。
样例
给出 1->2->3->4
, 你应该返回的链表是 2->1->4->3
。
你的算法只能使用常数的额外空间,并且不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
链表处理
链表的插入要正确处理,还要处理奇数个节点和偶数个节点的不同,细节都在注释里了,自己挑个小的链表画一下,主要是一些边界条件弄对就行了。
另外,我自己写链表的时候喜欢用假节点,不爱动链表本身,假节点初始化的时候一定要给一个值。c++不允许使用未初始化的对象。
ListNode * swapPairs(ListNode * head) {
if(head==NULL||head->next==NULL)
return head;
ListNode *first=new ListNode(0); //假表头,记得初始化
first->next=head;
ListNode *last=new ListNode(0); //最指向后一个元素,记得初始化
last->next=first;
ListNode *tmp;
while(head!=NULL)
{
tmp=head;
if(tmp->next==NULL)
//处理只剩一个的情况,要不下面取head=head->next->next的时候就会有野指针
{
Insert(last,tmp);
break;
}
head=head->next->next;
if(tmp->next!=NULL)
Insert(last,tmp->next);
Insert(last,tmp);
}
return first->next;
// write your code here
}
void Insert(ListNode *last,ListNode *l) //插入,last来记录最后一个节点的位置
{
ListNode *tmp1=last->next;
tmp1->next=l;
l->next=NULL;
last->next=l;
}
网友评论