asked on

merge sort for Linked List - pointers

Hi everyone,

I'm analyzing a code that merge two sorted linked list (the second part of the merge sort algorithm). But I can not understand this part:

splitLLInto2(head, &a, &b);

the pointers 'head', 'a' and 'b' were created at the same level of indirection ( node* head, node* a, node* b), the only difference is the pointer head which has already a value and 'a' and 'b' not yet.

Why is that happening? why not splitLLInto2(&head, &a, &b) or splitLLInto2(head, a, b) ? WHen I know that I have to pass the adress '&head' or just 'head' ?

thanks

void mergeSort(struct node** headRef) 
{
  struct node* head = *headRef;
  struct node* a;
  struct node* b;
 
  // Base case -- length 0 or 1
 
 
  if ((head == NULL) || (head->next == NULL)) 
  {
    return;
  }
  
  // Split head into 'a' and 'b' sublists
  splitLLInto2(head, &a, &b); 
 
  // Recursively sort the sublists
  mergeSort(&a); 
  mergeSort(&b);
 
  // Merge the two sorted lists together
  *headRef = merge2SortedLLs(a, b); 
}
 
 
 
 
 
void splitLLInto2(struct node* source, struct node** frontRef, struct node** backRef) 
{
  struct node* fast;
  struct node* slow;
  
  if (source==NULL || source->next==NULL) 
  { 
    // length < 2 cases
    *frontRef = source;
    *backRef = NULL;
  }
  else 
  {
    slow = source;
    fast = source->next;
    // Advance 'fast' two nodes, and advance 'slow' one node
    while (fast != NULL) 
    {
       fast = fast->next;
       if (fast != NULL) 
       {
          slow = slow->next;
          fast = fast->next;
       }
    }
    // 'slow' is before the midpoint in the list, so split it in two
    // at that point.
    *frontRef = source;
    *backRef = slow->next;
    slow->next = NULL;
  }
}

Open in new window

ASKER CERTIFIED SOLUTION

Infinity08

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

Johnson_sc

ASKER

right, right!
conclusion:

1) when I pass the address (&a), it means, I'm passing the address of the box/frame in the memory, and when this box/frame enter inside the function, I can change the value inside the box/frame and it will reflect out side the function, EVEN if I don't return nothing (it is implicit, right?)

2) if I pass just a value (it could be an int, char, an address pointed like 10x1, etc), I can do whatever I want because the function will treat locally... I can have this value modified inside to reflect outside, only if I return it.

3) mathematic is a perfect science.

thanks again infinity.

Infinity08

>> 1) when I pass the address (&a), it means, I'm passing the address of the box/frame in the memory, and when this box/frame enter inside the function, I can change the value inside the box/frame and it will reflect out side the function, EVEN if I don't return nothing (it is implicit, right?)

Apart from the non-standard terminology you use, I think you got it, yes :)

>> 2) if I pass just a value (it could be an int, char, an address pointed like 10x1, etc), I can do whatever I want because the function will treat locally... I can have this value modified inside to reflect outside, only if I return it.

Yes. This is because the function is working on a copy of the value, and any modifications to that copy have no impact on the original value.

>> 3) mathematic is a perfect science.

Heh :)