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
Consolidating random fun coding problems from novice level to the more advanced with links to the tutorials for the same.
// 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 } }
No. | Solution | Space Complexity | Time Complexity |
1. | Linear | O(1) | O(N) |
2. | Recursive | O(N) to allocate stack space | O(N) |
/* * 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 }