Почему эта функция сортировки слияния не вызывает бесконечный цикл?

Question

Я работаю над проектом, который требует от меня реализовать merge-sort в связанном списке, и я использую код из этого сообщения 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; 
} 

Answer 1

Это из предыдущей строки:

Node sHalf = middle.next; middle.next = null; 

В частности, middle.next = null; часть.

Поймите, что хотя указатель на голову тот же, , мы разбиваем список на половину, используя middle.next = null. Итак, в следующем рекурсивном вызове это только половина связанного списка, который был отправлен изначально.

И в какой-то момент он достигнет head.next == null состояние.