Java LinkedList split in half (Merge sort)

Question

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;
  }
}

Note that a bottom up merge sort for linked list avoids having to scan lists to split them. Instead a small (25 to 32) array of node references are used, where array[i] is either null or points to a list of 2^i nodes. — rcgldr
– rcgldr, Commented Jul 28, 2020 at 4:06

awi2b · Accepted Answer · 2020-07-27 23:34:24Z

1

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.

answered Jul 27, 2020 at 23:34

awi2b

571 silver badge7 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Papai from BEKOAIL · Accepted Answer · 2020-07-28 05:49:57Z

0

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.

answered Jul 28, 2020 at 5:49

Papai from BEKOAIL

1,5391 gold badge13 silver badges18 bronze badges

1 Comment

kzacharczyk Over a year ago

Thank you! that make sense!

Collectives™ on Stack Overflow

Java LinkedList split in half (Merge sort)

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related