题解 | #链表的奇偶重排#

C语言

//创建奇偶两条链表的虚拟头节点，根据当前节点的奇偶来放到对应奇偶链表中，当放完后，再将偶链表的放到奇链表后，输出

struct ListNode* oddEvenList(struct ListNode* head ) {

    // write code here

    struct ListNode* dummyHeadOdd  = (struct ListNode*)malloc(sizeof(struct ListNode));  //奇数虚拟头节点

    struct ListNode* dummyHeadEven = (struct ListNode*)malloc(sizeof(struct ListNode)); //偶数虚拟头节点

    struct ListNode *tmp, *tmpOdd, *tmpEven;

    tmp = head, tmpOdd = dummyHeadOdd, tmpEven = dummyHeadEven; //设置head和奇偶链表的当前位置指针

    int count = 0;

    while(tmp){

        count++;

        if(count%2){        //奇数，将head当前节点放到奇链表中

            tmpOdd->next = tmp;

            tmpOdd = tmpOdd->next;

        }else{              //偶数，将head当前节点放到偶链表中

            tmpEven->next = tmp;

            tmpEven = tmpEven->next;

        }

        tmp = tmp->next;

    }

    tmpEven->next = NULL;   //退出循环后，设置偶链表的下一位为空，防止嵌套

    tmpOdd->next = dummyHeadEven->next; //将偶链表的放到奇链表后

    return dummyHeadOdd->next;  

}