A Simple (?) linked list problem?

[fmcarthur]

I have a perplexing problem that I've been trying to solve ever since I screwed up an interview last week with a very high-profile famous company: 115K starting plus benefits. I went through a an initial tech screen, real-time code review, homework questions. I even passed the first initial in-person interview. It went downhill on the 2nd part of that interview. ALL GONE. THAT HURT! I've been hunting all over google and various computer science books for the answer to this supposedy simple question. Maybe it is simple?

A supposedly pretty basic(?) comp-sci question:

Given singly-linked list

struct Node
{
int stuff;
Node* pNext;
};


Problem: You have a link to a node somewhere in the middle. Reverse the entire linked list, starting at that node.

Out of desperation, I tried using recursion, building up the callstack, so I can reverse the nodes, writing them out to the middle as the callstack pops back. But of course, that only works for the middle node onward.

Using iteration, same result. I could never figure out how to get at the previous nodes, given the current middle node. I tried to use the current "middle" node as the previous node, then the middle->pNext as the current node, then somehow try to create a cycle that somehow implicity grabs previous nodes on each successive iteration.
But since I didn't really know exactly how to do it, I couldn't solve it.

Supposedly, it has an answer via an iterative technique. But I'm still just as lost as ever.

It would make me feel better knowing people who are far smarter than me also don't know how to do it. But it would be pretty cool if one of you knows the answer and would be kind enough to send me a C or pseudo-C -like example of a solution. (I prefer answers that compile and execute with no runtime errors, since most people who write pseudo-C don't even make pseudo-sense. Nevertheless, I'd be very grateful for any answers.)


Franklin

[R0mai]

[1]->[2]->[3]->[4]->[5]
           /\
           ||

Suppose -> are pointers, and you have a pointer to [3]. Following the arrows (pointers), you have no way to find [1] and [2].
Are you sure, the question wasn't about reversing [3],[4],[5], so that [2]'s pointer still points to a valid element (after reversing to [5])? In that case, it's very simple.

[guestgulkan]

Using the recursive method as a way of using the stack to store previous values - here is a solutuion.
(It the code code looks a bit untidy - it is just some code from the begineers section that someone posted that they were having problems with - I just chopped it about quickly) - So don't point out the memory leak....

#include<iostream>
#include<fstream>

using namespace std;



struct node
{ 
    int number;
    node *nxt;
};

node *start_ptr ;

void add( node * newNode)
{

    node *temp2 = start_ptr;

    if (start_ptr == NULL)
    { 
        start_ptr = newNode;
    }
    else
    { 
        while (temp2->nxt != NULL)
        {    
            temp2 = temp2->nxt;
        }
        temp2->nxt = newNode;
    }
}


void reverse(node *CurrentNode, node *OriginalStartNode )
{

    if(CurrentNode->nxt==0)
        return;

    if(CurrentNode->nxt->nxt !=0)
    {
        reverse(CurrentNode->nxt, OriginalStartNode);
    }

    else
    {
        OriginalStartNode->nxt = CurrentNode->nxt;
    }



    if(CurrentNode != OriginalStartNode)
    {
        CurrentNode->nxt->nxt= CurrentNode;
        CurrentNode->nxt =0;
    }


}


void display()
{
    node *cur_ptr = start_ptr;


    while(cur_ptr != NULL)
    {
        cout << cur_ptr->number << endl;
        cur_ptr = cur_ptr->nxt;
    }
}


int main()
{
    start_ptr = NULL;

    //add some nodes
    for (int count =1; count < 10; count++)
    {
        node *newNode = new node;

        newNode->number = count;
        newNode->nxt = 0;
        add(newNode);

    }

    display();//before the reversal
    //reverse from (but not including) a particular node.
    reverse(start_ptr->nxt, start_ptr->nxt);
    cout << endl;

    display();//after the reversal

} 

[AbstractionAnon]

Were you told if the list was circular, or terminated?

Using R0mai's example, if the list was circular, [5] points back to [1]. That makes it very simple. Just keep following the list until you get back to the starting element you were given [3].

If the list is null terminated ([5]'s pNext pointer is null), then you have no way to get back to [1].

If you weren't told and weren't allowed to ask for clarification, I would have assumed the list was circular.

[fmcarthur]

Hey guys, thanks very much for the replies.

Just to clarify:
For the given problem, I cannot assume that the nodes were allocated one right after the other (which would make it very easy to figure out the previous node: CurNode-1).

The end list node's pNext is null. No cycles.

I'm given a node somewhere in the middle of a singly linked list (anywhere from 1 to n-2) to start with. I do not have the address/location of any of the previous nodes.

And the problem is to reverse the entire list, including all the previous nodes: so that if the beginning of the list is:

1 -> 2 -> 3 -> 4 ->5. And the middle I'm given is 3 (for example)

The result is:

5 -> 4 -> 3 -> 2 -> 1


If I understand the above code answers correctly, the end result will always be:

5 -> 4 -> 3 (the previous nodes I can't get at still end up pointing to 3)

and

1 -> 2 -> 3 (the end node, 3, ends up being the tail of two singly-linked lists: one I can get at, and the other I still can't get at to reverse and "relink" correctly).

I welcome any/all replies/harsh criticism to set me straight.

Thanks again guys for replying.

Franklin