The topic of dry

Given a singly linked list, rank all the odd and even nodes together. Note that the odd and even nodes here refer to the parity of node numbers, not the parity of node values.

Try using the in situ algorithm. The space complexity of your algorithm should be O(1) and the time complexity should be O(Nodes), which is the total number of nodes.

Example 1:

Input: 1->2->3->4->5->NULL Output: 1->3->5->2->4->NULLCopy the code

Example 2:

Input: 1 - > 2 - > 3 - > 5 - > 4 - > 7-6 - > > NULL output: 2 - > 3 - > 6-7-1 - > > > 5 - > 4 - > NULLCopy the code

Source: LeetCode link: leetcode-cn.com/problems/od… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution: Make linked lists

The solution of this problem is very similar to that of separating linked lists in question 86. We still use two left and right linked lists for screening and then join to efficiently complete this problem.

Code implementation:

/** * 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 left = new ListNode(-1);
    let Right = new ListNode(-1);
    let leftCurrent = left;
    let rightCurrent = Right;
    let currentIndex = 1;
    while(head ! =null) {
        if (currentIndex % 2! =0) {
            let node1 = new ListNode(head.val);
            leftCurrent.next = node1;
            leftCurrent = leftCurrent.next;
        } else {
            let node2 = new ListNode(head.val);
            rightCurrent.next = node2;
            rightCurrent = rightCurrent.next;
        }
        head=head.next;
        currentIndex++;
    }
    // Join two odd-even lists
    leftCurrent.next=Right.next;
    return left.next
};
Copy the code