Skip to main content

Linked List Quiz - Part II !!!


In the last part, we saw the academic (not general purpose) version of a Linked List used to solve the puzzles, and solved the following puzzles on linked list.

  • Reverse the list recursively
  • Reverse the list iteratively
  • Find if a list is cyclic

In this part, I will be solving the remaining two puzzles that I listed in the last part.

Finding the cyclic node in a cyclic linked list
  1. According to my solution, the node which is actually supposed to be the end of the linked list is the cyclic node. Let us call Cn. Taking node Cn as the cyclic one has an advantage wherein you can break the cycle; assign Cn->next = nullptr;
  2. But some people take the node after Cn as the cyclic node. The node after Cn is the node somewhere back in the list. This way it is not possible to break the cycle as we would traversed past Cn.

LinkedList::Node* LinkedList::FindCyclicNode() const
{
   int iterCount = 0;

   auto jmpBy1Ptr = root;
   auto jmpBy2Ptr = root;

   while (jmpBy1Ptr != nullptr
      && jmpBy2Ptr != nullptr
      && jmpBy2Ptr->Next() != nullptr)
   {
      jmpBy1Ptr = jmpBy1Ptr->Next();
      jmpBy2Ptr = jmpBy2Ptr->Next()->Next();
      if (jmpBy1Ptr == jmpBy2Ptr)
      {
         const int noOfNodesInLoop = CountNoOfNodesInLoop(jmpBy1Ptr);
         cout << "No of nodes in loop: " << noOfNodesInLoop << std::endl;
         auto p1= root;
         auto p2 = GetNthNode(noOfNodesInLoop - 1); // zero based index
         cout << "Node at index " << noOfNodesInLoop << ": " << p2->Item() << std::endl;
         // Pointers meet at eye of the loop (this node is as per point #2 above)
         while (p1 != p2)
         {
            p1 = p1->Next();
            p2 = p2->Next();
         }
         // This piece of code takes you to the loop 
         // starting node (this node is as per #1 above)
         p2 = p2->Next();

         while(p2->Next() != p1)
         {
            p2 = p2->Next();
         }
         return p2;
      }
      ++iterCount;
   }

   return nullptr;
}

int LinkedList::CountNoOfNodesInLoop(Node* stopNode) const
{
 int count = 1;
 auto p1 = stopNode;
 auto p2 = stopNode;

 while (p1->Next() != p2)
 {
  p1 = p1->Next();
  ++count;
 }

 return count;
}

The code above is the result of several iterations of discussions with Azhagu. It wasn't written that way the first time. The first version was much complex and naive. I think it looks better now. What do you say?

Reversing every K nodes in the list: This is an interesting puzzle. You should not reverse the whole list instead only every K nodes, where N >= K > 1 and N is the number of nodes in the list. For instance, if you reverse 2 nodes (K = 2) in the following list

1 -> 2 -> 3 -> 4 -> 5 -> 6

the resulting list would be

2 -> 1 -> 4 -> 3 -> 6 -> 5

void LinkedList::Reverse(int k)
{
 prevHead = nullptr;

 auto head = root;
 root = _Reverse(head, k);
 head = head->Next();

 while (head != nullptr)
 {
  _Reverse(head, k);
  head = head->Next();
 }

 prevHead = nullptr;
}

LinkedList::Node* LinkedList::_Reverse(Node* head, int k)
{
 int iter = k;

 Node* current = head;
 Node* prev = nullptr;
 Node* next = nullptr;

 while (current != nullptr && iter >= 1)
 {
  next = current->Next();
  current->Next() = prev;

  if (next == nullptr)
  {
  break;
  }

  prev = current;
  current = next;
  --iter;
 }

 if (prevHead != nullptr)
 {
  prevHead->Next() = next != nullptr ? prev : current;
 }

 prevHead = head;
 head->Next() = next;

 return prev;
}

I hope the code covers all the corner cases of the puzzle. Give it a try and let me know if it all works for you.

1 comment

Popular posts from this blog

out, ref and InvokeMember !!!

When I was working on the .NET reflection extravaganza thing that I explained in my previous column, i learnt one another interesting thing, that is about the Type.InvokeMember. How will pass out or ref parameters for the method invoked using Type.InvokeMember ? If you are going to invoke a method with the prototypeint DoSomething(string someString, int someInt);then you would use InvokeMember like this:-object obj = someType.InvokeMember("DoSomething",
BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance,
null,
this,
new object[] {"Largest Integer", 1});or use some variables in the new object[] {...}. But what do you with the args if DoSomething takes out or ref parameters ?int DoSomething(out string someString, ref int someInt);Something like this will not work string someText = string.Empty;
int someInt = 0;
object obj = someType.InvokeMember("DoSomething",
BindingFlags.Public | BindingFlags.NonPublic …

Passing CComPtr By Value !!!

This is about a killer bug identified by our chief software engineer in our software. What was devised for ease of use and write smart code ended up in this killer defect due to improper perception. Ok, let us go!CComPtr is a template class in ATL designed to wrap the discrete functionality of COM object management - AddRef and Release. Technically it is a smart pointer for a COM object.void SomeMethod() { CComPtr siPtr; HRESULT hr = siPtr.CoCreateInstance(CLSID_SomeComponent); siPtr->MethodOne(20, L"Hello"); }Without CComPtr, the code wouldn't be as elegant as above. The code would be spilled with AddRef and Release. Besides, writing code to Release after use under any circumstance is either hard or ugly. CComPtr automatically takes care of releasing in its destructor just like std::auto_ptr. As a C++ programmer, we must be able to appreciate the inevitability of the destructor and its immense use in writing smart code. However there is a difference between …

jqGrid: Handling array data !!!

This post is primarily a personal reference. I also consider this a tribute to Oleg, who was fundamental in improving my understanding of the jqGrid internals - the way it handles source data types, which if I may say led him in discovering a bug in jqGrid.

If you are working with local array data as the source for jqGrid, meaning you will get the data from the server but want the jqGrid not to talk to the server anymore, and want to have custom handling of the edit functionality/form and delete functionality, it is not going to be straightforward - you need to have a decent understanding of how jqGrid works, and you should be aware of the bug Oleg pointed in our discussion. I repeat this is all about using jqGrid to manage array data locally, no posting to server when you edit or delete, which is where the bug is.

$('#grid').jqGrid('navGrid', '#pager', { recreateForm: true, add: false, search: false, refresh: false, …