Tuesday, May 8, 2012

Reverse Alternate Nodes in a Linked List

Q. Reverse Alternate Nodes in a Linked List.


Good Resource for the basics on linked lists (Linked List 101). 


Input.
A-->B-->C-->D-->NULL


Output
B-->A-->D-->C-->NULL

Possible Solutions: 
  • Alternate Node Data Swap. 
    • With two pointers(C1 and C2) we can point to the first node and second node and swap the Data in the two node and move the C1 to point to the third node and C2 to the fourth node and so on.
  • Alternate Node Swap.  
    • With three pointers C1, C2 and C3 pointed to A, B, C we can swap the first two nodes and then move the pointers to repeat the same.
  • Generic solution
    • Both are linear solutions but there is a fundamental flaw that we cannot expand this to swap three node or four nodes. 
    • A little more thought and it is the same as reversing 'N' lists of length 'K' were
    • E.g for a 3 way swap for input A-->B-->C-->D-->E-->NULL we reverse list 1 C-->B-->A and then E-->D-->NULL and join them to be            C-->B-->A-->E-->D-->NULL.
    • We already have the solution for reversing the linked list
    • We can extend the same for K-Reverse as following
C++ code
// Look at the Reversing linked list blog for class definitions, we are extending the same class here  
#include "linkedList.h"
void LinkedList::kReverseList(unsigned int k)
{
 
 Node* current = head;
 Node* tempHead = head;
 unsigned int counter = 1;
 while(NULL != current)
 {
  while(NULL != current && counter >= k)
  {
   current = current->next;
   counter++;
  }
 Node* tempNext = current->Next;
 Node* tail = head;     // Current Head will be tail node
 current->next = NULL;  // Break the linked list so that we can reverse it.
 nonRecursiveReverse(tempHead);
 tail->Next = tempNext; // Fix the list again.
 tempHead = tempNext;   // New Head node for the next list
 current = tempNext;
 counter = 1;           //Reset Counter
 }
}

3 comments:

  1. Hi I have a doubt. Once you have reversed the linked list in this fashion, how do you traverse it ? I mean you have to have a pointer to the head of the new list.

    ReplyDelete
  2. did u look at the link http://algopadawan.blogspot.com/2012/05/linked-list-reverse.html. This is a class method so the head pointer has been updated in the the reverse function and can be accessed. Makes sense?

    ReplyDelete
  3. Node * reverse_k_nodes(Node * node, int k){

    Node * current = node;
    Node *last_head = NULL;
    int t = k;
    /* Traversing K nodes */
    while(current && t--){
    current = current->next;
    }

    /* if there are more nodes in list, process them first
    by recursively calling the function*/
    if(current)
    last_head =reverse_k_nodes(current, k);

    /* At last, reverse the last K nodes and adjust next pointer. */
    Node * new_head = reverse_count(node, k);
    node->next = last_head;

    /* return the head pointer of the sub list just reversed. */
    return new_head;
    }

    For detailed explanation please refer to
    http://algorithmsandme.blogspot.in/2013/10/introduction-lets-take-break-from.html

    ReplyDelete