manipulating linked list

[junky_fellow]

Hi all,

I have a linked list in which each node is of follwoing type.

struct node {
struct node *fptr;
int data;
int flag; /* flag could be ORIG=1 or DUPLICATE=2 */
}

I need to write a function, that would manipulate the linked list so
that all the nodes
with flag = DUPLICATE are put at the end of the linked list.

for eg, let the original list be,
head---->DUPLICATE---->ORIG---->ORIG---->DUPLICATE ----->ORIG--->
NULL

The final list after manipulation should be,
head--->ORIG----->ORIG----->ORIG---->DUPLICATE------>DUPLICATE
------>NULL

Only requirement is that the nodes with flag = DUPLICATE should lie
at the end.

I don't want the exact code, I just need an algorithm or some hints.

Many thanks for any help in advance ...

 

[Eric Sosman]

Hi all,

I have a linked list in which each node is of follwoing type.

struct node {
struct node *fptr;
int data;
int flag; /* flag could be ORIG=1 or DUPLICATE=2 */
}

I need to write a function, that would manipulate the linked list so
that all the nodes
with flag = DUPLICATE are put at the end of the linked list.

for eg, let the original list be,
head---->DUPLICATE---->ORIG---->ORIG---->DUPLICATE ----->ORIG--->
NULL

The final list after manipulation should be,
head--->ORIG----->ORIG----->ORIG---->DUPLICATE------>DUPLICATE
------>NULL

Only requirement is that the nodes with flag = DUPLICATE should lie
at the end.

I don't want the exact code, I just need an algorithm or some hints.

Let the original list be L. Make two new lists L1,L2,
initially empty. Remove items from L one by one; append
each ORIG item to L1 and each DUPLICATE item to L2. Then
append L2 to L1 and return L1 as the result. Be careful of
boundary cases: L empty to begin with, L1 and/or L2 empty
after traversing L, etc.

 

[L7]

Hi all,

I have a linked list in which each node is of follwoing type.

struct node {
struct node *fptr;
int data;
int flag; /* flag could be ORIG=1 or DUPLICATE=2 */
}

I need to write a function, that would manipulate the linked list so
that all the nodes
with flag = DUPLICATE are put at the end of the linked list.

for eg, let the original list be,
head---->DUPLICATE---->ORIG---->ORIG---->DUPLICATE ----->ORIG--->
NULL

The final list after manipulation should be,
head--->ORIG----->ORIG----->ORIG---->DUPLICATE------>DUPLICATE
------>NULL

Only requirement is that the nodes with flag = DUPLICATE should lie
at the end.

I don't want the exact code, I just need an algorithm or some hints.

Many thanks for any help in advance ...

Original list == A
New list == B
While A not null:
if A.duplicate:
append to B
remove from A
end if
next A
end While
Append B to A

 

[Chris Torek]

Let the original list be L. Make two new lists L1,L2,
initially empty. Remove items from L one by one; append
each ORIG item to L1 and each DUPLICATE item to L2. Then
append L2 to L1 and return L1 as the result. Be careful of
boundary cases: L empty to begin with, L1 and/or L2 empty
after traversing L, etc.

There is a nice method of doing this in C that is difficult
in many other languages:

struct list *l1, *l2;
struct list **l1end = &l1, **l2end = &l2;
struct list *p;

for (p = orig_list; p != NULL; p = p->next) {
if (goes_in_l1(p)) {
*l1end = p;
l1end = &p->next;
} else {
*l2end = p;
l2end = &p->next;
}
}
*l2end = NULL;
*l1end = l2;

/* new list is now headed by l1 */

The order of the last two lines is important. (Exercise: why?)

 

[Bill Pursell]

There is a nice method of doing this in C that is difficult
in many other languages:

struct list *l1, *l2;
struct list **l1end = &l1, **l2end = &l2;
struct list *p;

for (p = orig_list; p != NULL; p = p->next) {
if (goes_in_l1(p)) {
*l1end = p;
l1end = &p->next;
} else {
*l2end = p;
l2end = &p->next;
}
}
*l2end = NULL;
*l1end = l2;

/* new list is now headed by l1 */

The order of the last two lines is important. (Exercise: why?)

assert(l1end->next == l2end);

A perfect demonstration of the right place to use assert!

<OT> I would call then temporary pointers l1head and l2head.
In other words, you can add things to the start of a list, but not
the end. I am apparently at odds with the rest of the universe on
this, but wasn't aware of it until a few months ago. When did
we start calling the head the "end"? Has it always been that way, or
am
I going insane? Does "head" imply "start" only to me?
</OT>

 

[CBFalconer]

I have a linked list in which each node is of follwoing type.

struct node {
struct node *fptr;
int data;
int flag; /* flag could be ORIG=1 or DUPLICATE=2 */
}

I need to write a function, that would manipulate the linked list
so that all the nodes with flag = DUPLICATE are put at the end of
the linked list.

Simply sort the list with mergesort, using 'flag' as the sort
field. You can find some examples in my published source at:

<http://cbfalconer.home.att.net/download/>

I suspect hashlib application examples will have suitable example
code.

 

[Chris Torek]

assert(l1end->next == l2end);

This should not even compile (unless you turn on NDEBUG), since
l1end->next has type "struct list *", while "l2end" has type
"struct list **".

<OT> I would call then temporary pointers l1head and l2head.
In other words, you can add things to the start of a list, but not
the end.

But that is not what they are; and this code *does* add things to
the end of each list. That is the tricky thing about l1end and
l2end: each time, it points to the "struct list *" that should
point to a new item in the corresponding list. Initially, the
"struct list *" that should point to the new items are "l1" and
"l2" respectively, but as items are added to those lists, they
change.

That is, initially, we have (l1end == &l1), but once there is
one item in list l1, we have (l1end == &l1->next). When there
are two items in list l1, we have (l1end == &l1->next->next),
and so on.

It is possible to avoid the need to set *l2end to NULL before
setting *l1end to l2, by initializing l2 to NULL at the top of the
code. The assignment to *l2end is then always redundant (in the
code shown above, it is redundant if and only if at least one item
has been placed into list l2).