题解 | 重排链表

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 *
 * @param head ListNode类
 * @return  void
 */
void reorderList(struct ListNode* head ) {
    //思路
    //使用快慢指针，将链表均分为两段，将后段逆序之后，依次插入前段：{123456} -> {123}{456} -> {123}{654} -> {162534}
    struct ListNode list1HeadNode = { .next = head };
    struct ListNode* fast = &list1HeadNode;
    struct ListNode* slow = &list1HeadNode;
    struct ListNode* list2Head = NULL;
    struct ListNode* nodeTmp = NULL;

    if ((head == NULL) || (head->next == NULL)) {
        return;
    }

    //使用快慢指针，将链表均分为两段
    while ((fast != NULL) && (fast->next != NULL)) {
        fast = fast->next->next;
        slow = slow->next;
    }

    //将后段原地逆序
    list2Head = slow->next;
    nodeTmp = list2Head->next;
    while (nodeTmp != NULL) {
        list2Head->next = nodeTmp->next;
        nodeTmp->next = slow->next;
        slow->next = nodeTmp;
        nodeTmp = list2Head->next;
    }

    //将后段结点依次间隔地插入前段
    nodeTmp = head;
    list2Head = slow->next;
    while ((nodeTmp != NULL) && (list2Head != NULL)) {
        slow->next = list2Head->next;
        list2Head->next = nodeTmp->next;
        nodeTmp->next = list2Head;
        nodeTmp = nodeTmp->next->next;
        list2Head = slow->next;
    }

    return;
}