排序奇升偶降链表

思路：

1.先根据奇数位和偶数位的节点拆分为两个表

2.再将第二个表进行反转

3.最后将第一个表和第二表进行合并

代码：

import java.util.*;

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

public class Solution {
    public ListNode Mergelist(ListNode head1,ListNode head2){
        //将两个链表进行合并，如果其中的一个链表为空，就直接返回另一个链表即可
        if(head1==null){
            return head2;
        }
        if(head2==null){
            return head1;
        }
        //否则就先让newhead指定为两个节点中较小的节点
        //让otherhead指定为两个节点中较大的节点
        ListNode newhead=(head1.val>=head2.val)?head2:head1;
        ListNode otherhead=(head1.val>=head2.val)?head1:head2;
        //设置三个指针变量，进行两表合并，先找到大于需要插入的节点值的节点，将这个节点插入到那个节点的前面
        //否则就一直往后找
        ListNode cur1=newhead.next;
        ListNode cur2=otherhead;
        ListNode cur1_pre=newhead;
        while(cur1!=null&&cur2!=null){
            if(cur1.val>cur2.val){
                cur1_pre.next=cur2;
                cur2=cur2.next;
                cur1_pre.next.next=cur1;
                cur1_pre=cur1_pre.next;
            }else{
                cur1_pre=cur1;
                cur1=cur1.next;
            }
        }
        //如果发现cur1为空，cur2不为空，则就是说明cur2的最大值大于cur1的最大值，所以插在cur1表的最后
        if(cur2!=null){
            cur1_pre.next=cur2;
        }
        return newhead;
    }
    public ListNode Reverselist(ListNode head2){
        //如果发现需要反转的链表没有节点或者只有一个节点，就不需要进行反转，直接返回
        if(head2==null||head2.next==null){
            return head2;
        }
        //否则就进行反转链表
        ListNode pre=null;
        ListNode cur=head2;
        ListNode cur_next;
        while(cur!=null){
            cur_next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=cur_next;
        }
        return pre;
    }
    public ListNode sortLinkedList (ListNode head) {
        //如果发现需要需要排序的链表只有一个节点或者是一个空表，那么就可以直接不需要处理直接返回
        if(head==null||head.next==null){
            return head;
        }
        //按照奇偶位将链表一分为二
        ListNode head1=head;
        ListNode head2=head.next;
        ListNode cur1=head1;
        ListNode cur2=head2;
        while(cur2!=null&&cur2.next!=null){
            cur1.next=cur2.next;
            cur1=cur1.next;
            cur2.next=cur1.next;
            cur2=cur2.next;
        }
        //注意需要将分开来的两个表的尾结点都指向null
        cur1.next=null;
        //将偶位的节点构成的链表进行反转
        head2=Reverselist(head2);
        //最后将两个分开来的链表进行合并
       return  Mergelist(head1,head2);

        
    }
}