java 归并排序链表

package wangChaoPA实习工作练习.com.leetcode;

/**
*
* <p>
* 描述该类情况 {@link 代表跟谁有关系}
* </p>
*
* @author 王超
* @since 1.0
* @date 2017年5月10日下午8:16:20
* @see 新建|修改|放弃
* @see wangChaoPA实习工作练习.com.leetcode.Sort_List 归并排序链表算法先寻找链表的中节点,然后根据中节点进行分割
* ,对每一部分递归地应用归并排序.在两部分都排好序后,对它们进行归并
*/

//链表类
class ListNode
{
   ListNode next;// 下一个节点
   int val;// 值

   ListNode(int x)
   {// 构造方法
       this.val = x;
       this.next = null;
   }
}

public class Sort_List
{
   // 返回中结点
   static ListNode getMiddleOfList(ListNode head)
   {
       ListNode slow = head;
       ListNode fast = head;
       // slow走一步 ,fast走两步最后的slow就是中点快慢指针
       while (fast.next != null && fast.next.next != null)
       {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
   }

   // 测试的方法
   public static void main(String[] args)
   {
       ListNode list1 = new ListNode(9);
       ListNode list2 = new ListNode(8);
       ListNode list3 = new ListNode(6);
       ListNode list4 = new ListNode(7);
       ListNode list5 = new ListNode(10);
       list1.next = list2;
       list2.next = list3;
       list3.next = list4;
       list4.next = list5;
       list5.next = null;
       ListNode temp = sortList(list1);
       while (temp.next != null)
       {
           System.out.println("++++" + temp.val);
           temp = temp.next;
       }
   }

   // 排序
   static ListNode mergeList(ListNode a, ListNode b)
   {
       ListNode dummyHead = new ListNode(-1);// 假的头节点
       ListNode curr = dummyHead;// temp是个对象改变curr的值就是改变temp中的值
       while (a != null && b != null)
       {
           if (a.val <= b.val)
           {
               curr.next = a;
               a = a.next;
           }
           else
           {
               curr.next = b;
               b = b.next;
           }
           curr = curr.next;
       }
       curr.next = (a != null) ? a : b;
       return dummyHead.next;// 返回第一个真正的节点
   }

   // 主要方法
   public static ListNode sortList(ListNode head)
   {
       // 如果head为空或其next为空直接返回head
       if (head == null || head.next == null)
       {
           return head;
       }
       // 中点
       ListNode middle = getMiddleOfList(head);
       ListNode next = middle.next;// 中点的下一点
       middle.next = null;// 分割链表
       return mergeList(sortList(head), sortList(next));// 递归调用
   }
}

java 归并排序 链表

java 归并排序链表