leetcode 143. Reorder List

143. Reorder List:题目链接

AC code:

struct ListNode*  reverse(struct ListNode* head){
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;
    while (cur != NULL){
        next = cur->next;
        cur->next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

void reorderList(struct ListNode* head){
    if (head == NULL || head->next == NULL){
        return;
    }
    struct ListNode* dummyHead = (struct ListNode*) malloc(sizeof(struct ListNode));
    dummyHead->next = head;
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast->next != NULL && fast->next->next!= NULL) {
        slow = slow->next; // 一次移动一个
        fast = fast->next->next; // 一次移动2个
    }
    

    struct ListNode* p = slow;
    // p指向链表中间节点 从链表头到p形成一个链表dummyHead  从p的后一个节点到尾节点形成一个链表q
    // 逆转中间往后部分的链表 q = reverse(p->next)
    struct ListNode* q = p->next;
    if (q == NULL) {
        return head;
    }
    q = reverse(q); //逆转之后新的链表
    p->next = NULL; //置空
    
    // 合并dummyHead 、q两个链表乘一个新的链表
    p = dummyHead->next;
    struct ListNode* tail = dummyHead;
    int flag = 0;
    while (p != NULL && q != NULL) {
        if (flag == 0) {
            tail->next = p;
            tail = p;
            p = p->next;
            flag = 1;
        }else{
            tail->next = q;
            tail = q;
            q = q->next;
            flag = 0;
        }
    }
    
    if (p != NULL) {
        tail->next = p;    
    }
    
    if (q != NULL) {
        tail->next = q;    
    }
    return dummyHead->next;
}

/*
Runtime: 16 ms, faster than 92.53% of C online submissions for Reorder List.
*/