Reversing a linked list using double pointer and swapping

Please review:
    https://www.experts-exchange.com/help.jsp?hi=21

@phoffric: Thank you. I'm not looking to solve a homework question. been a while since i've been out of school. But I'm a beginner to C. I've done both these methods separately. i.e.: swapping 1st with last etc. and using a double pointer for the same. I'm trying to combine both considering I have knowledge of the number of elements.
Let me rephrase this question. Maybe you can help me through it.

If you take a stab at what you are trying to do, then one of us will try to give you the requested guidance. Post the code in the Code box, and if it does not work, then be sure to ask a specific question indicating what you expected and what went wrong.

BTW, what OS and compiler (or IDE) are you using?

If you are self-studying, then to benefit from this process, it is important to show us what you have so that we can comment on your approach.

In my article C++ Q & A / Interview Practice Questions I explain how to reverse a list...


Question: Given the following function signature, write a function to reverse a linked list?

void reverse_single_linked_list(struct node** headRef);

Select allOpen in new window

T
Answer: Ideally, something like the following...

void reverse_single_linked_list(struct node** headRef)
{
   struct node* result = NULL;
   struct node* current = *headRef;
   struct node* next;

   while (current != NULL)
   {
       next = current->next; // tricky: note the next node
       current->next = result; // move the node onto the result
       result = current;
       current = next;
   }

   *headRef = result;
}

Select allOpen in new window

Starting from the head of the list for each iteration we make the next pointer of the 'current' node point to the previous node, we have to keep track of the 'next' node so as not to lose it as well as the 'result', which will end up being the new head once the complete list has been reversed.

Let's see how that works...

KEY
-------------------
H : Head
N : Node
C : Current
X : Next
R : Result
0 : Null terminator

Iteration 0

X ---> ?
C ---> H
R ---> 0

H ---> N1 ---> N2 ---> 0

Iteration 1

X ---> N1
C ---> N1
R ---> H

0 <--- H      N1 ---> N2 ---> 0

Iteration 2

X ---> N2
C ---> N2
R ---> N1

0 <--- H <--- N1      N2 ---> 0

Iteration 3

X ---> 0
C ---> 0
R ---> N2

0 <--- H <--- N1 <--- N2

It says "swapping the contents" so you actually would just start and both ends and swap whatever is in the first and last node that isn't pointers. Then just keep going until you meet.

So if your node is something like

class Node
{
  Node* next;
  Node* prev;
  Contents contents;
};

Select allOpen in new window

Then you'd just do something like this (You'll have to convert this to fit your code so that should help solidify it)

Node* n1 = head;
Node* n2 = tail;
Contents temp;

while(n1 != n2 && n1->next != n2)
{
  temp = n1->contents;
  n1->contents = n2->contents;
  n2->contents = temp;
}

Select allOpen in new window

It's really quite simple.

I've requested that this question be deleted for the following reason:

This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.

In http:#a35346675 I gave the simple easy solution in English and then elaborated in more detail with code examples in http:#a35346711 and clarified some typos in http:#a35346734
These posts represent a perfect solution to the problem given.

mlmcc, the problem said to swap the first and last etc effectively reversing the list. Clearly the reversal must be done using swapping of contents otherwise the first solutions would have been fine and I wouldn't have posted anything. The way the question was worded looks like a textbook problem so the 'right' way to do it won't work here.

Actually since all memory has been allocated, you can't use a temp variable so it can't be done.

I guess the real issue is whether the list was doubly linked as you assumed or just singly linked as evilrix assumed. Also there is no tail pointer provided so you would have to walk the list to get it.

I agree it appears to be an assignment or book problem.

mlmcc

You could actually use the a^=b^=a^=b trick to swap without any extra memory, but this is clearly a lower level assignment and "assume all memory has been allocated" means you don't have to do any allocation yourself, not that it's all used up.

Also, the question title says "double pointer." I don't know what else that could be except a doubly linked list.

To me double pointer indicates you have a pointer to the head and a pointer to some other place probably the next element or in this case the element to swap with.

Since the asker accepted your comment it would seem it is a doubly linked list.

mlmcc