通用单链表中的归并排序
Merge sort in generic single linked list
在排序时遇到一些问题,在调试时,我发现有趣的事情是在方法 Merge 中 return 数据是正确的,然后它加入到 MergeSortLL方法并显示 Head 那里只有一个节点,而它必须有 ex。 5 排序节点。我能在这里错过什么?
public static LinkedListNode<T> MergeSortLL<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head == null || Head.Next == null)
return Head;
LinkedListNode<T> middle = GetMiddle(Head);
LinkedListNode<T> half = middle.Next;
middle.Next = null;
return Merge(MergeSortLL(Head), MergeSortLL(half));
}
public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{
var mHead = new LinkedListNode<T>(default(T));
LinkedListNode<T> curr = mHead;
while (Left != null && Right != null)
{
if (Left.Value.CompareTo(Right.Value) <= 0)
{
curr.Next = Left;
Left = Left.Next;
}
else
{
curr.Next = Right;
Right = Right.Next;
}
curr = curr.Next;
}
curr.Next = (Left == null) ? Right : Left;
return mHead.Next;
}
public static LinkedListNode<T> GetMiddle<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head == null)
{
return Head;
}
LinkedListNode<T> slow, fast;
slow = fast = Head;
while (fast.Next != null && fast.Next.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
What could I miss here?
您遗漏了该方法修改了链接和 returns 新 头部,因此旧头部显示更少或零的下一个元素是正常的。
如果换成这个会更明显
return Merge(MergeSortLL(Head), MergeSortLL(half));
和
Head = Merge(MergeSortLL(Head), MergeSortLL(half));
return Head;
也不要忘记在外部调用中做同样的事情,例如
LinkedListNode<int> head = ...;
head = MergeSortLL(head);
在排序时遇到一些问题,在调试时,我发现有趣的事情是在方法 Merge 中 return 数据是正确的,然后它加入到 MergeSortLL方法并显示 Head 那里只有一个节点,而它必须有 ex。 5 排序节点。我能在这里错过什么?
public static LinkedListNode<T> MergeSortLL<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head == null || Head.Next == null)
return Head;
LinkedListNode<T> middle = GetMiddle(Head);
LinkedListNode<T> half = middle.Next;
middle.Next = null;
return Merge(MergeSortLL(Head), MergeSortLL(half));
}
public static LinkedListNode<T> Merge<T>(LinkedListNode<T> Left, LinkedListNode<T> Right) where T : IComparable<T>
{
var mHead = new LinkedListNode<T>(default(T));
LinkedListNode<T> curr = mHead;
while (Left != null && Right != null)
{
if (Left.Value.CompareTo(Right.Value) <= 0)
{
curr.Next = Left;
Left = Left.Next;
}
else
{
curr.Next = Right;
Right = Right.Next;
}
curr = curr.Next;
}
curr.Next = (Left == null) ? Right : Left;
return mHead.Next;
}
public static LinkedListNode<T> GetMiddle<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head == null)
{
return Head;
}
LinkedListNode<T> slow, fast;
slow = fast = Head;
while (fast.Next != null && fast.Next.Next != null)
{
slow = slow.Next;
fast = fast.Next.Next;
}
return slow;
}
What could I miss here?
您遗漏了该方法修改了链接和 returns 新 头部,因此旧头部显示更少或零的下一个元素是正常的。
如果换成这个会更明显
return Merge(MergeSortLL(Head), MergeSortLL(half));
和
Head = Merge(MergeSortLL(Head), MergeSortLL(half));
return Head;
也不要忘记在外部调用中做同样的事情,例如
LinkedListNode<int> head = ...;
head = MergeSortLL(head);