Parity rearrangement of Bm14 linked list

subject

The title comes from Niuke
describe
Given a single chain table , Please set a function , Put the odd and even nodes of the linked list together , Output after rearrangement . Note that it is the number of the node, not the value of the node .

Example 1
Input ：
{1,2,3,4,5,6}

Return value ：
{1,3,5,2,4,6}

explain ：
1->2->3->4->5->6->NULL
After rearrangement
1->3->5->2->4->6->NULL

Example 2
Input ：
{1,4,6,3,7}

Return value ：
{1,6,7,4,3}

explain ：
1->4->6->3->7->NULL
After rearrangement
1->6->7->4->3->NULL
Odd nodes have 1,6,7, Even bit nodes have 4,3. After rearrangement 1,6,7,4,3

remarks ：
The length of the linked list is not greater than 200000. Each number range is int Inside .

Ideas

According to the title , You can find out odd digit linked list and even digit linked list , Then the last node of the odd linked list next Point to the head node of the even digit linked list , You can string them .
First, you need to save the even number of header nodes , namely resDouble. When traversing the linked list, you can ignore while The execution condition of the loop , Write logic first .

Now let's look at the ergodic condition ,while First used in singleNode and doubleNode Of next, Then make sure that singleNode and doubleNode It can only be taken if it is not empty next, and doubleNode If it is not empty singleNode It must not be empty , because doubleNode yes singleNode Of next, So first add the condition doubleNode != null. And conditions doubleNode.next != null Because if it is empty , Then the odd linked list is shown in the figure above 1 Move to 3 after , There is no need to take it again 3 Of next Assigned to the next node of the even numbered linked list . therefore while On the condition that while(doubleNode != null && doubleNode.next != null).

Code

import java.util.*;

/* * public class ListNode { * int val; * ListNode next = null; * public ListNode(int val) { * this.val = val; * } * } */

public class Solution {
    
    /** *  The class name in the code 、 Method name 、 The parameter name has been specified , Do not modify , Return the value specified by the method directly  * * @param head ListNode class  * @return ListNode class  */
    public ListNode oddEvenList (ListNode head) {
    
        // write code here
        if(head == null || head.next == null){
    
            return head;
        }
        ListNode resDouble = head.next;
        ListNode singleNode = head;
        ListNode doubleNode = head.next;
        while(doubleNode != null && doubleNode.next != null){
    
            singleNode.next = doubleNode.next;
            singleNode = singleNode.next;
            doubleNode.next = singleNode.next;
            doubleNode = doubleNode.next;
        }
        singleNode.next = resDouble;
        return head;
    }
}