reorder list

leetcode-reorder_list

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void reorderList(ListNode *head) {
        /*判断提前短路情况*/
        if(head==0||head->next==0||head->next->next==0)
            return;
        /*快慢指针得到中间节点*/
        ListNode *fast=head;
        ListNode *slow=head;
        while(fast!=0&&fast->next!=0){
            fast=fast->next->next;
            slow=slow->next;
        }
        
        ListNode *middle=slow;
        ListNode *second=middle->next;
        middle->next=0;
        
        /*second链表反转，我这里采用申请一个头结点的方式*/
        ListNode *second_head=(ListNode *)malloc(sizeof(ListNode));
        second_head->next=0;second_head->val=-1;
        
        /*我这采用的是头插法，但是头插法和尾插真正的区别在什么地方*/
        ListNode *temp=0;
        while(second!=0){
            temp=second;
            second=second->next;
            temp->next=second_head->next;
            second_head->next=temp;
        }
        
        head=merge(head,second_head->next);
    }
    
    ListNode *merge(ListNode *left,ListNode *right){
        ListNode *head=left;
        left=left->next;
        ListNode *tail=head;
        
        ListNode *left_temp,*right_temp;
        /*在此我们要使用尾插法了*/
        while(left!=0&&right!=0){
            left_temp=left;
            right_temp=right;
            left=left->next;
            right=right->next;
            right_temp->next=0;
            tail->next=right_temp;
            tail=tail->next;
            left_temp->next=0;
            tail->next=left_temp;
            tail=tail->next;
        }
        
        if(left!=0){
            left->next=0;
            tail->next=left;
            tail=tail->next;
        }
        
        if(right!=0){
            right->next=0;
            tail->next=right;
            tail=tail->next;
        }
        
        return head;
    }
};

首先这道题，我一次完成，没有调试！然后这题有需要注意的几点：
1，快慢指针
2，链表反转（头插法）
3，尾插法