Oct 202012
 

We have seen a question to rotate an array around a pivot earlier. Now write similar code for linked list.

Given a linked list and an integer value ‘k’. Write a code to rotate linked list by k nodes from the end, as shown in the below diagram for k=2

Note that k nodes are counted from the end (and not from start) of the list.

Solution:

This is a really simple question. We need three pointers

1. ptrNewLast, Pointing to the (k+1)'th Node from end (which will be the last node of rotated list).
2. ptrNewHead, pointing to the Node next to ptrNewLast, which will be the head of rotated list.
3. ptrOrigLast, pointing to the last Node in the Original list.

Once these pointers are set,  all we have to do is

// Breaking list at k'th position
ptrNewLast->link = NULL;

// Making last point to the head
ptrOrigLast->link = head;

// Setting head to new First node
head = ptrNewHead;

Code:

/**
 * Passing the head by reference. 
 * If you are writing C language code then pass it as Node**
 * 
 * Structure of Node is
 * 
 * struct Node
 * {
 *    int data;
 *    Node* link;  
 * };     
 */   
void rotateList(Node *& head, unsigned int k)
{
    if (k == 0){ return; }

    Node* temp = head;

    // Counting total number of nodes in list
    unsigned int totalNodes = 0;
    while(temp!= NULL){
        temp = temp->link;
        totalNodes++;
    }

    if(totalNodes <= k){ return; }

    Node* ptrNewLast = NULL;
    Node* ptrNewHead = NULL;
    Node* ptrOrigLast = NULL;

    // Making ptrNewLast point to (k+1)'th Node From end
    ptrNewLast = head; 
    for(unsigned int i=0; i<(totalNodes-k-1); i++)
        ptrNewLast = ptrNewLast->link;

    ptrNewHead = ptrNewLast->link;

    // setting the ptrOrigLast pointer to the last Node in original list
    ptrOrigLast = ptrNewHead;
    while(ptrOrigLast->link != NULL)
        ptrOrigLast = ptrOrigLast->link;        

    // Breaking list at k'th position
    ptrNewLast->link = NULL;

    // Making last point to the head
    ptrOrigLast->link = head;

    // Setting head to new First Node
    head = ptrNewHead;
}

Time Complexity: O(n)

The function has many scope of improvements:

  • Does not need the temp variable, we can manipulate with the three pointers only. For that matter we can get away with variable ‘ptrNewHead’ also.
  • May reduce the number of iterations if we set the variables in the first loop itself (while counting the total number of elements in the list.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)