Solved

# merge sort for Linked List - pointers

Posted on 2009-04-01
404 Views
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:

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* a;
struct node* b;

// Base case -- length 0 or 1

{
return;
}

// Split head into 'a' and 'b' sublists

// Recursively sort the sublists
mergeSort(&a);
mergeSort(&b);

// Merge the two sorted lists together
}

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;
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;
}
}
``````
0
Question by:Johnson_sc
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 2

LVL 53

Accepted Solution

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 */
``````
0

Author Comment

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

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

Question has a verified solution.

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

### Suggested Solutions

basic hardware to learn oop advanced design patterns 3 120
C Programming - If Statement 8 84
outlook office 365 8 171
.NET Core supports which cell phone platforms? 3 33
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
###### Suggested Courses
Course of the Month8 days, 8 hours left to enroll