public class ListNodeMergeSort {
public static class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
}
public ListNode(){
}
public void setVal(int x){
this.val = x;
}
public int getVal(){
return this.val;
}
}
public ListNode merge(ListNode list1, ListNode list2){
ListNode dummyList = new ListNode(-1);
// 临时变量
ListNode tmp = dummyList;
ListNode tmp1 = list1;
ListNode tmp2 = list2;
// 开始有序合并
while (tmp1!=null && tmp2!=null){
if(tmp1.val<tmp2.val){
tmp.next = tmp1;
tmp1 = tmp1.next;
}else{
tmp.next = tmp2;
tmp2 = tmp2.next;
}
tmp = tmp.next;
}
// 剩余链表合并
if (tmp1!=null){
tmp.next = tmp1;
}else if(tmp2!=null){
tmp.next = tmp2;
}
return dummyList.next;
}
public ListNode sortList(ListNode head, ListNode tail){
// 节点为空
if(head == null){
return head;
}
// 只有一个节点
if(head.next == tail){
head.next = null;
return head;
}
// 开始找到中点
ListNode fast = head;
ListNode slow = head;
while (fast!=tail){
fast = fast.next;
slow = slow.next;
if(fast!=null){
fast = fast.next;
}
}
// 划分为head->mid-1 mid->tail
ListNode mid = slow;
ListNode list1 = sortList(head,mid); //mid为下一个链表的开始
ListNode list2 = sortList(mid, tail);
ListNode sorted = merge(list1, list2); //合并两个有序的链表
return sorted;
}
public ListNode sortList(ListNode head){
return sortList(head, null);
}
public static void main(String[] args) {
ListNode head = new ListNode(5);
ListNode cur = head;
for(int i=5;i>=0;i--){
cur.next = new ListNode(i);
cur = cur.next;
}
// 排序之前
ListNode tmp = head;
System.out.println("排序之前");
while (tmp!=null){
System.out.printf(tmp.val+ " ");
tmp = tmp.next;
}
System.out.println();
// 排序之后
ListNodeMergeSort listNodeMergeSort = new ListNodeMergeSort();
head = listNodeMergeSort.sortList(head);
tmp = head;
System.out.println("排序之后");
while (tmp!=null){
System.out.printf(tmp.val+ " ");
tmp = tmp.next;
}
System.out.println();
}
}
