Rearrange a linked list in Zig-Zag

Rearrange a given linked list such that it should be in form a < b > c < d > e < f > for linked list with a, b, c, d, e, f as nodes.

Example

Time complexity : O(n)

Algorithm

a. Traverse the linked list from head.

b. Create a variable flag (Boolean value).

1. If flag is true then the next node of current should be greater. If not swap them.

2. If flag is false then the next node of current should be smaller. If not swap them.

c. While traversing, change the value of flag every time we move one position ahead.

d. The final list is the desired list.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

void ZigZag(struct LLNode *head)
{
    bool flag = true;
 
    // Traverse linked.
    struct LLNode* curr = head;//start from head
    while (curr->next != NULL)
    {
        //Condition is X > Y > Z swap Y and Z
        //convert to X > Z < Y or Z < Y with no X
        if(flag)
        {
            if (curr->data > curr->next->data)
            {
                swap(curr->data, curr->next->data);
            }
        }
        //Condition is X < Y < Z swap Y and Z
        //convert to X < Z > Y or Z > Y with no X
        else
        {
            if (curr->data < curr->next->data)
            {
                swap(curr->data, curr->next->data);
            }
        }
        //Move forward by reversing flag
        curr = curr->next;
        flag = !flag;
    }
    //O(number of nodes)
}
  
//Main function
int main(void)
{
    struct LLNode* head = NULL;
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 4);
 
    cout<<"Input linked list is: ";
    display(&head);
    ZigZag(head);
    cout<<"'\nOutput linked list is: ";
    display(&head);
 
    return (0);
}

 

Translate »