奇偶链表

奇偶链表

题目描述

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

示例

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

分析

• 先建立 odd 和 even 指针，分别指向的是奇链表, 偶链表
• 建立 p 和 q, 指向 odd 和 even
• 遍历 head 链表，odd.next 指向 head, even.next = head.next, 就是说一次遍历直接跳两个元素
• 修改 head 指向 head = head.next.next, 但此时需要判断 head.next是否为null
• 修改 odd 和 even, odd = odd.next; even = even.next;
• 最后修改 odd.next 指向 even 的开头即可

题解

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
    let odd = new ListNode("head", null);
    let even = new ListNode("head", null);

    let p = odd;
    let q = even;

    while(head) {
        odd.next = head;
        even.next = head.next ? head.next : null
        head = head.next && head.next.next ? head.next.next : null;
        odd = odd.next;
        even = even.next;
    }  
    odd.next = q.next;
    return p.next;

};