LeetCode:Reorder List

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