链表排序：算法-归并排序public class LinkedSort {    private static class ListNode {        int val;        ListNode next;        ListNode(int x) {            val = x;            next = null;        }    }    private ListNode mergeList(ListNode head1,ListNode head2){        if(head1==null){            return head2;        }else if(head2==null){            return head1;        }        ListNode head=new ListNode(0);        ListNode tmp=head;        while(head1!=null&&head2!=null){            if(head1.val<=head2.val){                head.next=head1;                head1=head1.next;            }else{                head.next=head2;                head2=head2.next;            }            head=head.next;        }        while(head1!=null){            head.next=head1;            head1=head1.next;            head=head.next;        }        while(head2!=null){            head.next=head2;            head2=head2.next;            head=head.next;        }        return tmp.next;//注意另起一个新的节点    }    public ListNode sortList(ListNode head) {        if(head==null||head.next==null){            return head;        }        ListNode first=head;        ListNode after=head;        // two nodes要特别处理是两个节点的情况        if(head.next.next==null){            first=head.next;            head.next=null;            return mergeList(head, first);        }                while(after!=null){            if(after.next!=null){                after=after.next.next;                first=first.next;            }else{                break;            }        }        ListNode tmp=first.next;        first.next=null;//这里容易出现问题，提前将后置节点归null        ListNode head1=sortList(head);        ListNode head2=sortList(tmp);        return mergeList(head1, head2);    }    public static void main(String[] args){        LinkedSort linkedSort=new LinkedSort();        ListNode head1=new ListNode(9);        head1.next=new ListNode(3);        head1.next.next=new ListNode(4);        head1.next.next.next=new ListNode(1);        head1.next.next.next.next=new ListNode(5);        ListNode head=linkedSort.sortList(head1);        System.out.println("fuck");        while(head!=null){            System.out.println(head.val);            head=head.next;        }            }}