Change the order of nodes in a singly linked list
Let's say we have a list 1-2-3-4-5 (list values can be in no order, for example 2-4-5-3-1);
The challenge is to reorder the list nodes (not values) as follows: 1-5-2-4-3.
I wrote a function that uses 2 temporary variables and 1 pointer. But the problem is that I don't know how to set the "next" pointer in the penultimate node to "NULL" without defining the second temp pointer in the function. Is there a more efficient way to do this?
void Swap(Node* begin)
{
if (begin->next != NULL || begin->next->next != NULL)
{
Node temp1 = *begin; //this variable is used for iteration
Node* temp2 = begin; //pointer to the target node
Node prev; //get the adress of last node
while (temp1.next != NULL)
{
prev = temp1;
temp1 = *temp1.next;
}
prev.next->next = temp2->next;
temp2->next = prev.next;
Swap(prev.next->next);
}
}
source to share
You can use this algorithm: o (n) time complexity
- Count the number of nodes (n) in the list.
- Push the last n / 2 nodes onto the stack.
- Start moving the list from the beginning.
- For each item that is moved, pop an item off the stack and make it the next item in the moved item.
- Do this until the stack is empty.
-
Remember to change the next node next pointer to NULL.
(In case of odd counting, you need to traverse one more item even if the stack is empty)
source to share
So basically what you want to do:
N0, N1, ..., Nm -> N0, Nm, N1, Nm-1, ..., Nm/2 if m is even
-> N0, Nm, N1, Nm-1, ..., N(m-1/2), N(m+1/2)
you can possibly traverse your list from i in (m/2 +1)..m
(in reverse order) (assuming m is equal) remove the node and insert it in i+1
'th place
or step through your list from i in (m/2 +1)..m
(assuming m is equal to) remove the node and insert it into m-i+1
'th place
source to share