K Reverse a linked list

Q. K-Reverse a linked list.

• Examples. 
• Input. (K = 2)   A-->B-->C-->D-->E-->NULL
• Output (K = 2)  B-->A-->D-->C-->E-->NULL
• Input. (K = 3)   A-->B-->C-->D-->E-->NULL
• Output (K = 3)  C-->B-->A-->E-->D-->NULL

This problem is discussed in here

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
 }
}

Linked List Reverse

Q. How to reverse a linked list.

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

Possible Solutions: 

• Linear Solution

          Consider the following linked list ( A-->B-->C-->D-->NULL) the expected output is (D-->C-->B-->A-->NULL).

• • With one pointer to the Node 'A' say current we can access the node 'A' and node 'B'. (current-->next). If we point the next node for B to A we get the following (A-->B-->A) however we lose the next node 'C' and also have a loop A-->B-->A information.
  • We can fix this by trying with 2 extra nodes. Node 'prev' points to A and node current points to B. So we can break the node link A-->B and point B-->A ( current points to prev) however we still lose the node C information.
  • Lets us try this approach now with 3 nodes. prev = NULL , current = A, next = B. We continue traversing to the end of the list while updating the 'current' node to point to 'prev' and moving the (prev, current and next nodes by one)

• Recursive Solution 
  • This solution is more intutive. We are essentially trying to traverse till the end of the list and point each node next to its previous node i.e. traverse the list from the TAIL node (D here) D to C to B to A.
  • We use the same logic as above however we now recurseively traverse the linked list till the end of loop and point the current node to the prev node. 
  • In the above example we recurse till current = 'D' and prev is 'C' then point the current D next to C i.e. D-->C.
  • When we come of out the recursive call end noe current is C and prev is B so C-->B, so on till the head node

• Analysis of Solutions 

No.	Solution	Space Complexity	Time Complexity
1.	Linear	O(1)	O(N)
2.	Recursive	O(N) to allocate stack space	O(N)

C++ code

/*
 * LinkedList.h
 *
 *  Created on: Jul 6, 2011
 *  Author: vivekrajumuppalla
 */
#pragma once

#define NULL 0

class Node{
private :
 int m_data;
 Node* m_next;
public:
 Node(int data);
 ~Node();
 int getNodeData();
 Node* getNodeNext();
 void setNextNode(Node* nextNode);
};

Node::Node(int data)
{
 m_data = data;
 m_next = NULL;
}

Node::~Node()
{
 if(NULL != m_next)
 {
  delete m_next;
 }
}

int Node::getNodeData()
{
 return m_data;
}

Node* Node::getNodeNext()
{
 return m_next;
}

void setNextNode(Node* nextNode)
{
 m_next = nextNode;
}

include "listNode.h"
#pragma once

class LinkedList
{
public:
 LinkedList();
 ~LinkedList();
 void recursiveReverse(Node*& headNode);
 void nonRecursiveReverse();

private:
 Node* head;
}

#include "linkedList.h"
void LinkedList::nonRecursiveReverse()
{
        Node* prev = NULL;
 Node* current = head;
 Node* next = NULL;

 while(NULL != current)
 {
  next = current->getNodeNext();
  current->setNextNode(prev);
  prev = current;
  current = next;
 }
 head = prev;
}

// reference needed since we have to update the node not just its pointer 
void LinkedList::recursiveReverse(Node*& headNode) 
{
 if(NULL == headNode || NULL == headNode->getNodeNext())
 {
  tail = headNode;
  return;
 }
 Node* nextNode = headNode->getNodeNext();
 recursiveReverse(nextNode);
 nextNode->setNextNode(headNode);
 headNode->setNextNode(NULL); // This will cause last node to point to NULL
}