就是用 List 来实现 merge sort.
- import java.io.*;
- import java.util.*;
- class ListNode {
- int val;
- ListNode next;
- ListNode(int x) {
- val = x;
- next = null;
- }
- static ListNode initializeLinkList(ArrayList<Integer> arrList){
- ListNode head = new ListNode(arrList.get(0));
- ListNode cNode = head;
- for(int i=1;i<arrList.size();i++)
- {
- cNode.next = new ListNode(arrList.get(i));
- cNode = cNode.next;
- }
- return head;
- }
- static void showList(ListNode head)
- {
- while(head != null)
- {
- System.out.println(head.val);
- head = head.next;
- }
- }
- }
- public class Solution {
- public ListNode medianNode(ListNode head)
- {
- ListNode osNode = head;
- ListNode tsNode = head;
- while(tsNode.next != null && tsNode.next.next !=null)
- {
- osNode = osNode.next;
- tsNode = tsNode.next.next;
- }
- return osNode;
- }
- public ListNode mergeList(ListNode head1, ListNode head2)
- {
- if(head1 == null)
- return head2;
- else if(head2 == null)
- return head1;
- ListNode head = null, cnode = null;
- if(head1.val < head2.val)
- {
- head = head1;
- head1 = head1.next;
- }
- else
- {
- head = head2;
- head2 = head2.next;
- }
- cnode = head;
- while(head1 != null && head2 != null)
- {
- if(head1.val < head2.val)
- {
- cnode.next = head1;
- head1 = head1.next;
- }
- else
- {
- cnode.next = head2;
- head2 = head2.next;
- }
- cnode= cnode.next;
- }
- while(head1 != null)
- {
- cnode.next = head1;
- cnode = cnode.next;
- head1 = head1.next;
- }
- while(head2 != null)
- {
- cnode.next = head2;
- cnode = cnode.next;
- head2 = head2.next;
- }
- return head;
- }
- public ListNode sortList(ListNode head) {
- if(head == null || head.next == null)
- return head;
- ListNode mNode = medianNode(head);
- ListNode head1 = head;
- ListNode head2 = mNode.next;
- mNode.next = null;
- head1 = sortList(head1);
- head2 = sortList(head2);
- head = mergeList(head1,head2);
- return head;
- }
- }
来源: http://www.bubuko.com/infodetail-2067517.html