这道题明显不是很难,但莫名其妙的总是出现WA,最后直接重写了一遍还是没发现哪里错了,好歹还是AC了。
首先按题目要求,我们分几步走,先把整个链表拆成两半,要保证前面节点比后面多。然后将后面部分的链表反转,最后将得到的后半部分链表依次有间隔的插入前半部分的链表中。
利用快慢指针可以讲链表拆成两半,然后用迭代递归方法都可以反转链表,间隔插入元素也很简单。
class Solution { public: ListNode* reverseList(ListNode* head){ if(head==NULL||head->next==NULL)return head; //如果head为NULL或者只有一个元素 ListNode* cur=head->next; //记录当前指针指向位置 ListNode* pre=head;//记录当前指针的前一个位置 ListNode* ne; while(cur!=NULL){ ne=cur->next;//辅助指针,指向当前指针的后一个位置 cur->next=pre;//当前指针指向前一个位置 pre=cur;//pre指针后移一个位置 cur=ne;//当前位置往后移一个位置 } head->next=NULL;//head指针指向最后的元素,head->next=NULL return pre; } void reorderList(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. if(head==NULL || head->next==NULL) return; ListNode* pslow=head;//慢指针 ListNode* pfast=head; //快指针 ListNode* pre=head;//记录慢指针位置,为后半部分链表的表头 while(pfast!=NULL&&pfast->next!=NULL){ pre=pslow; pslow=pslow->next;//慢指针步长为1 pfast=pfast->next->next;//快指针步长为2 } ListNode* head2; //保证前面节点数量比后面多 if(pfast==NULL){ head2 = pslow; pre->next=NULL; } else if(pfast->next==NULL){ head2 = pslow->next; pslow->next = NULL; } head2 = reverseList(head2); //反转链表 ListNode* ans = head; ListNode* tmp1 = head; ListNode* tmp2 = head2; while(ans!=NULL&&tmp2!=NULL){ tmp1=ans->next; tmp2=head2->next; ans->next=head2; head2->next=tmp1; ans=tmp1; head2=tmp2; } } };
LeetCode:Reorder List,布布扣,bubuko.com
原文:http://blog.csdn.net/whu_sky/article/details/22745599