合并排序链接列表

Question

我最近重新整理了一些基本知识，发现合并对链表进行排序是一个非常好的挑战。如果您有一个好的实现，那么请在此处展示它。

Answer 1

想知道为什么它应该是这里所说的巨大挑战，这是Java中没有任何“聪明把戏”的简单实现。

//The main function

public static Node merge_sort(Node head) 

{

    if(head == null || head.next == null) 

        return head;

    Node middle = getMiddle(head);      //get the middle of the list

    Node left_head = head;

    Node right_head = middle.next; 

    middle.next = null;             //split the list into two halfs

    return merge(merge_sort(left_head), merge_sort(right_head));  //recurse on that

}

//Merge subroutine to merge two sorted lists

public static Node merge(Node a, Node b)

{

    Node dummyHead = new Node();

    for(Node current  = dummyHead; a != null && b != null; current = current.next;)

    {

        if(a.data <= b.data) 

        {

            current.next = a; 

            a = a.next; 

        }

        else

        { 

            current.next = b;

            b = b.next; 

        }

    }

    current.next = (a == null) ? b : a;

    return dummyHead.next;

}

//Finding the middle element of the list for splitting

public static Node getMiddle(Node head)

{

    if(head == null) 

        return head;

    Node slow = head, fast = head;

    while(fast.next != null && fast.next.next != null)

    {

        slow = slow.next;

        fast = fast.next.next;

    }

    return slow;

}