首页 > 其他 > 详细

LeetCode:Reorder List

时间:2014-04-02 09:06:59      阅读:409      评论:0      收藏:0      [点我收藏+]

这道题明显不是很难,但莫名其妙的总是出现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

LeetCode:Reorder List

原文:http://blog.csdn.net/whu_sky/article/details/22745599

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!