CODEWITHSUNDEEP
calgorithmdata-structureslinked-list
ihjn
ihjn

Reputation: 45

Change the order of nodes in a single-linked list

Say we have a list 1-2-3-4-5 (values of list can be without order, for example 2-4-5-3-1);
The task is to reorder nodes of list (not values) in the way like this: 1-5-2-4-3.
I wrote the function that uses 2 temporary variables and 1 pointer. But the problem is I don't know how to set the "next" pointer in penultimate node to "NULL" without defining the second temporary pointer in 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);
    }

}

Upvotes: 3

Views: 2430

Answers (2)

Othman Benchekroun
Othman Benchekroun

Reputation: 2018

so basically What you want to do is this :

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 maybe walk your list from i in (m/2 +1)..m (in reverse) (assuming m is even) remove the node and insert it in the i+1'th place

or walk your list from i in (m/2 +1)..m (assuming m is even) remove the node and insert it in the m-i+1'th place

Upvotes: 0

Shobhit_Geek
Shobhit_Geek

Reputation: 597

You can use this algorithm: o(n) time complexity

  1. Count the no of nodes(n) in list.

  2. Put the last n/2 nodes in a stack.

  3. Start traversing the list from the starting.

  4. For each traversed element, pop the element from stack and make it the next element of the traversed element.

  5. Do this until stack gets empty.

  6. Keep in mind to change the last node next pointer to NULL.

    (In case of odd count you have to traverse one more element even if stack is empty)

Upvotes: 1

Related Questions