I'm using C compiler in unix. We have created a linked list and know
that one of the node does not point to next node but point to one of
the previous node. How can I find this node?

Marcus

: I'm using C compiler in unix. We have created a linked list and know
: that one of the node does not point to next node but point to one of
: the previous node. How can I find this node?

Walk the list printing out the nodes contents?  I've missed something
somewhere, I think.

Will

typedef struct node {
        struct node *next;
        /* whatever other data */

PNODE   FindNode(void)
{
        PNODE   p, q;

        for (p = Head, q = NULL; p; p = p->next) {
                if (p->next == q)
                        return p;
                q = p;
        }
        return NULL;

"Walk" the list and stop at each node. Pick up the pointer to the next
node. Look back over the portion of the list you've traveled so far and
see if the pointer you're holding is to any of those nodes (or to the
current node). If not, go to the next node and repeat.

If you have difficulty making the code work, post it here with
description of problem.

Morris Dovey
West Des Moines, Iowa USA

        node_t* find_node(node_t* head) {

                for (; head; head= head->next) {

                        head->mark= 1;

                        if (head->next && head->next.mark)
                                break;
                }

                return head;
        }

If there's no such thing as a 'mark field', things get a bit more
complicated,
but not all is lost -- the following function traverses a list (with a
loop
somewhere) using _two_ pointers p and q. Pointer p hops from an element
to the next element, while pointer q hops two elements at the time; when
the two pointers compare equal again, pointer p has traversed the loopy
part of the list once. While hopping the list every value of p's next
value
is checked agains a value r. Here it is:

        node_t* hop_list(node_t* r) {

                node_t* p= r;
                node_t* q= r;

                do {
                        if (p->next == r)
                                return p;

                        p= p->next;
                        q= q->next->next;
                }
                while (p != q);

                return NULL;
        }

The function above can be used to find the back-pointing element:

        node_t* find_back(node_t* head) {

                for (; head; head= head->next) {

                        if (hop_list(head) == head)
                                return head;
                }

                return NULL;
        }

kind regards,