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.

Comments

Popular posts from this blog

Implementing COM OutOfProc Servers in C# .NET !!!

Had to implement our COM OOP Server project in .NET, and I found this solution from the internet after a great deal of search, but unfortunately the whole idea was ruled out, and we wrapped it as a .NET assembly. This is worth knowing. Step 1: Implement IClassFactory in a class in .NET. Use the following definition for IClassFactory. namespace COM { static class Guids { public const string IClassFactory = "00000001-0000-0000-C000-000000000046"; public const string IUnknown = "00000000-0000-0000-C000-000000000046"; } /// /// IClassFactory declaration /// [ComImport(), InterfaceType(ComInterfaceType.InterfaceIsIUnknown), Guid(COM.Guids.IClassFactory)] internal interface IClassFactory { [PreserveSig] int CreateInstance(IntPtr pUnkOuter, ref Guid riid, out IntPtr ppvObject); [PreserveSig] int LockServer(bool fLock); } } Step 2: [DllImport("ole32.dll")] private static extern int CoR

Extension Methods - A Polished C++ Feature !!!

Extension Method is an excellent feature in C# 3.0. It is a mechanism by which new methods can be exposed from an existing type (interface or class) without directly adding the method to the type. Why do we need extension methods anyway ? Ok, that is the big story of lamba and LINQ. But from a conceptual standpoint, the extension methods establish a mechanism to extend the public interface of a type. The compiler is smart enough to make the method a part of the public interface of the type. Yeah, that is what it does, and the intellisense is very cool in making us believe that. It is cleaner and easier (for the library developers and for us programmers even) to add extra functionality (methods) not provided in the type. That is the intent. And we know that was exercised extravagantly in LINQ. The IEnumerable was extended with a whole lot set of methods to aid the LINQ design. Remember the Where, Select etc methods on IEnumerable. An example code snippet is worth a thousand

sizeof vs Marshal.SizeOf !!!

There are two facilities in C# to determine the size of a type - sizeof operator and Marshal.SizeOf method. Let me discuss what they offer and how they differ. Pardon me if I happen to ramble a bit. Before we settle the difference between sizeof and Marshal.SizeOf , let us discuss why would we want to compute the size of a variable or type. Other than academic, one typical reason to know the size of a type (in a production code) would be allocate memory for an array of items; typically done while using malloc . Unlike in C++ (or unmanaged world), computing the size of a type definitely has no such use in C# (managed world). Within the managed application, size does not matter; since there are types provided by the CLR for creating\managing fixed size and variable size (typed) arrays. And as per MSDN, the size cannot be computed accurately. Does that mean we don't need to compute the size of a type at all when working in the CLR world? Obviously no, else I would