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

核心思想

• 链表长度<=2的，直接返回
• 定义初始结点，分别指向第一个奇数结点，和第二个偶数节点
• 循环，判断条件是当前偶数节点是否有下一个奇数结点
  • 有奇数结点，则完善奇数链表，也就是摘掉当前的偶数节点，移动奇数链表尾结点
  • 完事后，继续判断是否有偶数节点
    • 有偶数节点，则完善偶结点链表
    • 没有偶数节点，则终结偶数链表，即尾结点next = null
• 奇数尾巴结点追加偶数头指针
• 返回原始头，head

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @return ListNode类
 */

struct ListNode* oddEvenList(struct ListNode* head ) {
    // write code here
    if(head == NULL || head->next == NULL || head->next->next == NULL)
    {
        return head;
    }
    
    
    struct ListNode * even = head;
    struct ListNode * evenMove = even;
    struct ListNode * odd = head->next;
    struct ListNode * oddMove = odd;
    
    while(oddMove->next != NULL)
    {
        evenMove->next = oddMove->next;
        evenMove = evenMove->next;
        
        if(evenMove->next == NULL)
        {
            oddMove->next = NULL;
            break;
        }
        oddMove->next = evenMove->next;
        oddMove = oddMove->next;
    }
    
    
    evenMove->next = odd;
    return head;
}