题解 | 链表的奇偶重排

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类
 * @return ListNode类
 */
struct ListNode* oddEvenList(struct ListNode* head ) {
    //思路
    //对超过2个结点的原链表进行重排，以第1结点为奇数结点的起始插入点，第2结点为偶数结点的起始插入点
    //从第3个结点开始，将奇数序号的结点依次插入奇数插入点

    struct ListNode *oddInsertNode = NULL;
    struct ListNode *moveNode = NULL; //操作结点
    struct ListNode *moveNodePre = NULL; //操作结点
    int cnt = 3;

    if (head == NULL || head->next == NULL || head->next->next == NULL) {
        //不超过2个结点，直接输出
        return head;
    }

    oddInsertNode = head;
    moveNodePre = head->next;
    moveNode = moveNodePre->next;

    while (moveNode) {
        if (cnt % 2 != 0) { //将奇数序号的结点依次放置在奇数插入点后
            moveNodePre->next = moveNode->next;
            moveNode->next = oddInsertNode->next;
            oddInsertNode->next = moveNode;
            moveNode = moveNodePre->next;

            oddInsertNode = oddInsertNode->next; //后移奇数插入点
        } else { //偶数结点不动
            moveNodePre = moveNodePre->next;
            moveNode = moveNodePre->next;
        }

        cnt++;
    }
    return head;
}