Solved

merge sort for Linked List - pointers

Posted on 2009-04-01
3
400 Views
Last Modified: 2012-05-06
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

0
Comment
Question by:Johnson_sc
  • 2
3 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 250 total points
ID: 24040374
Since you are assigning a value to *frontRef and *backRef inside the function that has to be visible outside the function :

>>     *frontRef = source;
>>     *backRef = NULL;

you need to pass a pointer-to-pointer-to-node. You're passing the values by pointer, so that any changes to them will remain visible after the function ends.

Since the source node does not need to be modified by the function, you can simply pass it like that.

You can look at it like this : source is the input parameter for the function, and frontRef and backRef are the two output parameters for the function.


It's the same as what's happening here :
void fun(int a, int *b) {

  a = 5;

  *b = 5;

}
 

int a = 0;

int b = 0;

fun(a, &b);

/* at this point, a will still have the value 0, but b will have the value 5 */

Open in new window

0
 

Author Comment

by:Johnson_sc
ID: 24040710
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.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24041075
>> 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 :)
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

895 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!

Get 1:1 Help Now