为什么这个合并排序函数不会导致无限循环?
Why doesn't this merge-sort function cause an infinite loop?
我正在做一个需要我在链表上实现合并排序的项目,我正在使用这个 post Here 中的代码来帮助我。有人可以解释为什么在第 6 行,当我调用 return merge(merge_sort(head),merge_sort(sHalf));
方法 merge_sort(head)
时,其中包含相同的头指针的方法不会导致无限循环吗?在我看来,它是用同一个头指针重新开始的。
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.info <= b.info) { 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 sHalf = middle.next; middle.next = null;
具体来说,middle.next = null;
部分。
了解即使头指针相同,我们将列表分成两半,使用middle.next = null
。所以,在接下来的递归调用中,原来发送的链表只有一半。
并且在某一时刻,它将达到head.next == null
条件。
我正在做一个需要我在链表上实现合并排序的项目,我正在使用这个 post Here 中的代码来帮助我。有人可以解释为什么在第 6 行,当我调用 return merge(merge_sort(head),merge_sort(sHalf));
方法 merge_sort(head)
时,其中包含相同的头指针的方法不会导致无限循环吗?在我看来,它是用同一个头指针重新开始的。
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.info <= b.info) { 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 sHalf = middle.next; middle.next = null;
具体来说,middle.next = null;
部分。
了解即使头指针相同,我们将列表分成两半,使用middle.next = null
。所以,在接下来的递归调用中,原来发送的链表只有一半。
并且在某一时刻,它将达到head.next == null
条件。