Leetcode question brushing - parity linked list 328 medium

Discussion and source code of odd and even linked list
     The title of the parity linked list is shown in the figure below , This question belongs to the linked list and search type , Mainly investigate the use of search methods and the understanding of linked list structure . The title of this article, the author thought 2 Methods , They are recursive search method and double pointer method , Where recursive search uses Java Compiling , The double pointer method uses Python Compiling , Of course, this may not be the optimal solution , I also hope you guys can give a faster algorithm .

     I think this problem can be solved by using the idea of recursive search , First, judge whether the list is empty , If yes, return null directly . Then initialize to get odd number of header nodes and even number of header nodes , And record the odd number of header nodes , Start calling recursive functions to search , Inside a recursive function , It mainly determines whether the even node or the next node after the even node is empty , If yes, it will directly return to the even node ; Otherwise, point the even node to the next node of the odd node , Then point the odd node to the next node of the even node , And continue to recursively call until the end of the search and return the final linked list results . Then according to this idea, our Java The code is as follows ：

# Fire breathing dragon and water arrow turtle 
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null){
            return null;
        }  
        ListNode one = head;
        ListNode two = head.next;
        ListNode twoHead = two;
        rev(one,two).next = twoHead;
        return head;
    }
    private ListNode rev(ListNode one,ListNode two){
        if(one.next == null || one.next.next == null)
            return one;
        one.next = two.next;
        two.next = one.next.next;
        return rev(one.next,two.next);
    }
}

     obviously , We see that the recursive search method works well , At the same time, the double pointer method can also be used to solve . First, judge whether the list is empty , If yes, it directly returns null , Then record even nodes , And get odd nodes and even nodes , Then traverse the even nodes , When the even node is not empty and the next node under the even node is not empty , Point the odd node to the next node of the even node , Move the odd node to the next position ; Point the even node to the next node of the odd node , Move even nodes to the next location . Finally, until the end of the traversal , Point the odd linked list to the even linked list , It is the merged result and returns . So according to this idea, we can solve , Here is Python Code ：

# Fire breathing dragon and water arrow turtle 
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if(not head):
            return head
        evenHead = head.next
        odd =  head
        even = evenHead
        while even and even.next:
            odd.next = even.next
            odd = odd.next
            even.next = odd.next
            even = even.next
        odd.next = evenHead
        return head

     As a result Java The efficiency of this version of recursive search method is good , and Python The speed of the version of the double pointer method is also OK , But there should be more ways to further speed up , I hope friends can give me more advice , Thank you very much .