Reversing a linked list using double pointer and swapping

Write a section of c code to iterate through a list, swapping the contents of the 1st element with the last, 2nd with 2nd to
last, etc. This is effectively reversing the order of the list.

The list can be referenced via the variables below, assume all
memory has already been allocated.

void **head;
int num_elements;
gvashistAsked:
Who is Participating?

[Product update] Infrastructure Analysis Tool is now available with Business Accounts.Learn More

x
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

phoffric\Commented:
gvashistAuthor Commented:
@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.
phoffric\Commented:
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?
Become a Microsoft Certified Solutions Expert

This course teaches how to install and configure Windows Server 2012 R2.  It is the first step on your path to becoming a Microsoft Certified Solutions Expert (MCSE).

phoffric\Commented:
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.
evilrixSenior Software Engineer (Avast)Commented:
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);

Open 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;
}

Open 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
TommySzalapskiCommented:
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.

TommySzalapskiCommented:
So if your node is something like
class Node
{
  Node* next;
  Node* prev;
  Contents contents;
};

Open 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;
}

Open in new window


It's really quite simple.
TommySzalapskiCommented:
Oh, yeah, you also need to add n1=n1->next and n2=n2->prev
The n1 != n2 && n1->next != n2 is needed because if the list has an odd number of elements then n1 will equal n2 at some point, if it's even then they will pass each other.

You actually need to flip what I originally had. Should be n2->next != n1 since they do need to pass.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
mlmccCommented:
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.
TommySzalapskiCommented:
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.
TommySzalapskiCommented:
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.
mlmccCommented:
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

TommySzalapskiCommented:
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.
mlmccCommented:
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.