我最近重新整理了一些基本知識，發(fā)現(xiàn)合并對鏈表進行排序是一個非常好的挑戰(zhàn)。如果您有一個好的實現(xiàn)，那么請在此處展示它。
3 回答
斯蒂芬大帝
TA貢獻1827條經(jīng)驗 獲得超8個贊
想知道為什么它應該是這里所說的巨大挑戰(zhàn)，這是Java中沒有任何“聰明把戲”的簡單實現(xiàn)。
//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;
}
添加回答
舉報
0/150
提交
取消