Java实现单链列表的合并类型

由于链表（LinkedList）不支持随机访问（Random Access）java 链表java 链表，因此仅允许顺序访问，因此对于链表具有O（logn）时间复杂度的排序算法，您不能使用基于随机访问的排序算法例如快速排序和合并排序可以满足此需求.

合并排序是分而治之的典型应用. 伪代码如下:

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

以下Java代码实现了单个链接列表（单链接列表）的合并排序，该代码实现精美，易读且具有较高的参考价值:

// The main function
public Node merge_sort(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node middle = getMiddle(head); // get the middle of the list
    Node sHalf = middle.next;
    middle.next = null; // split the list into two halfs
    return merge(merge_sort(head), merge_sort(sHalf)); // recurse on that
}
// Merge subroutine to merge two sorted lists
public Node merge(Node a, Node b) {
    Node dummyHead, curr;
    dummyHead = new Node();
    curr = dummyHead;
    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) ? b : a;
    return dummyHead.next;
}
// Finding the middle element of the list for splitting
public Node getMiddle(Node head) {
    if (head == null) {
        return head;
    }
    Node slow, fast; //“快慢指针”
    slow = fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

链表节点Node的定义如下:

public class Node {
    public Node next;
    public int val;
}

原始链接:

链接到本文:

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-205271-1.html