Java LinkedList split in half (Merge sort)

huangapple go评论71阅读模式
英文:

Java LinkedList split in half (Merge sort)

问题

Currently, I am learning about merge sort with Linked List. I don't understand well how to split the original ListNode in half.

I cannot understand clearly why ListNode left = mergeSort(head); isn't head the entire original ListNode, not only the left half? And why does the method getMiddleNode only return slowptr?

As I assume, ListNode left = mergeSort(head); only contains the left half, but I want to understand how head is only becoming half. Thank you!

Here is my code:

class Solution {
  public ListNode mergeSort(ListNode head) {
    if (head == null || head.next == null) {
      return head;
    }
    
    ListNode middle = getMiddleNode(head);
    
    ListNode left = mergeSort(head);
    ListNode right = mergeSort(middle);
    
    return merge(left, right);
  }
  
  ListNode getMiddleNode(ListNode head) {
    ListNode pre = null;
    ListNode slowptr = head;
    ListNode fastptr = head;
    
    while (fastptr != null || fastptr.next != null) {
      pre = slowptr;
      slowptr = slowptr.next;
      fastptr = fastptr.next.next;
    }
    
    pre.next = null;
    return slowptr;
  }
}

(Note: I've provided the translation without the code, as requested.)

英文:

currently I am learning about merge sort with Linked List. I don't understand well how to split the original ListNode in half.

I cannot understand clearly why ListNode left = mergeSort(head); isn't head entire original ListNode not only left half? and why method getMiddleNode only return slowptr?

as I assume, ListNode left = mergeSort(head); only contains left half but I want to understand how head is only become half.

Thank you!

Here is my code

class Solution {
  public ListNode mergeSort(ListNode head) {
    if(head == null || head.next == null){
      return head;
    }
    
    ListNode middle = getMiddleNode(head);
    
    ListNode left = mergeSort(head);
    ListNode right = mergeSort(middle);
    
    return merge(left, right);
  }
  
  ListNode getMiddleNode(ListNode head)
  {
    ListNode pre = null;
    ListNode slowptr = head;
    ListNode fastptr = head;
    
    while(fastptr != null || fastptr.next != null)
    {
      pre = slowptr;
      slowptr = slowptr.next;
      fastptr = fastptr.next.next;
    }
    
    pre.next = null;
    return slowptr;
  }
}

答案1

得分: 1

I cannot understand clearly why ListNode left = mergeSort(head); isn't
head entire original ListNode not only left half?

因为使用 pre.next = null; 将中间节点之前的节点的下一个节点设置为 null,这导致原链表的前半部分(从头到 pre,包括 pre)与后半部分(从中间到末尾,包括中间)之间不再存在链接,它们成为了两个独立的链表。

and why method getMiddleNode only return slowptr?

因为在循环后,slowptr 指向链表的中间节点。slowptr 和 fastptr 都初始化为 head,然后一起"遍历"链表。但是,fastptr 的移动速度是 slowptr 的两倍(fastptr = fastptr.next.next; 而不是 slowptr = slowptr.next;),所以当 fastptr 到达链表末尾时,slowptr 已经走了一半的路程,即在中间。

英文:

> I cannot understand clearly why ListNode left = mergeSort(head); isn't
> head entire original ListNode not only left half?

with pre.next = null; the following node of the node before the middle node is set to null, so there dosnt exist an link between first half of the linkedList (from head to pre, inklusiv) and the second half(from middle to end, inklusiv), so they have become two independent lists.

> and why method getMiddleNode only return slowptr?

because after the loop, slowptr is pointing to the node in the middle of the linkedList. slowptr and fastptr are initialised as head, and then both "walk" throug the list. But fastptr at double the speed of slowptr (fastptr = fastptr.next.next; instead of slowptr = slowptr.next;), so when fastptr is at the end, slowptr has done half the way <=> is in the middle.

答案2

得分: 0

你可以清楚地理解为什么 ListNode left = mergeSort(head); 只包含列表的左半部分,通过在 getMiddleNode(head); 之后打印 head 就可以明白。

原因在于,在 getMiddleNode(head) 函数中,你将列表分成两半。当你通过递归一遍又一遍地执行相同的操作时,你会得到列表的左半部分,其边界是当前的中间位置,而右半部分恰恰相反(即列表的右半部分,其边界是当前中间位置到当前最后一个元素)。

例如,假设这是你要应用归并排序的初始列表:
11->8->3->35->4

在执行 getMiddleNode(head) 后,你会得到两个列表,如下所示:

11->8->3(左侧)和35->4(右侧)

现在,如果我们再次调用相同的函数,我们会得到:

11(左侧)和8(右侧)[用于前一个左侧部分]

35和4(用于前一个右侧部分)[用于前一个右侧部分]

现在,对于前一个右侧部分找到了基本情况,我们可以对其进行排序/交换操作,同样对于前一个左侧部分的右侧部分(即3)也是如此。

到目前为止,我们的列表是:3, 4, 35

如果我们对前一个左侧部分的左侧部分(11->8)应用相同的逻辑,我们会得到:

11(左侧)和8(右侧)

现在,对于当前列表再次找到了基本情况,因此我们可以对它们进行排序,最终我们会得到:

3 4 8 11 35。

这就是传奇归并排序的工作原理。

英文:

You can clearly understand why ListNode left = mergeSort(head); is contains only left part of the list, by printing head right after getMiddleNode(head);

The reason, is you're spliting the list into two halves in getMiddleNode(head) function. and When you are doing same thing over and over again by recursion, consecutively, you will get left half of the list, whose boundary is current middle, and exactly opposite for right half (i.e., right half of the list whose boundary is current middle to current-last-element).

For example, consider this one is your initial list, in which you want to apply merge sort.
11->8->3->35->4

after getMiddleNode(head), you will get two list like following:

11->8->3(left) and 35->4(right)

now if we call same function one more time we'll get:

11->8(left) and 3(right) [ for prev left part]

35 and 4 (for prev right part) [for prev right part]

now for prev right part base case found, we can sort/swap it,
likewise, same is true for right of prev left part, that is 3.

so till now, our list is: 3, 4, 35

if we apply same logic over left of prev left part(11->8), we will get:

11(left) and 8(right)

now base case found again for current list, so we can make them sort, and finally we will get,

3 4 8 11 35.

that's how legendary merge sort works.

huangapple
  • 本文由 发表于 2020年7月28日 06:51:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/63124745.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定