Check if the given list is palindrome

You are given with the singly linked list of say having characters, you have to tell whether the list is palindrome or not.

The list is palindrome when if you iterate the list from both the ends it should generate the same string. This problem can be solved in multiple ways. Some of the approaches are discussed here.


Approach 1: Brute force

• Generate the string out of the list. 
• Now check if the list is palindrome, by simple traversing the string from both the ends and comparing each character during traversal.

This approach has many shortcomings such as space required and multiple traversals for palindrome confirmation.

 

Approach 2: Reverse the list from middle

• Find out the mid element of the list by using two pointer ( slow will increment once, fast will increment twice).
• From the middle to the end reverse the list. 
• Now use two pointers one pointing to the start of the list and other pointing to middle of the list. 
• Then iterate list till middle ( from start) comparing each element from middle till end.

In this approach we have overhead of reversing the list. If we are not allowed to modify the list then we will have to revert back the modification done.

 

Approach 3: Use recursion

• Use the reference pointer variable.
• Use slow and fast pointers to reach till middle of the list using recursion.
• Now once we have reached to the middle of the list, assign the middle element to the reference pointer variable.
• Now while coming back from the recursion, compare at each step the element with the reference variable value. 
• Point to the next node of reference variable and come out of recursion.

This is sort of reversing of the list but here we are not modifying the list. But this method will require the stack space for recursion equal to the half of the size of the list.
Advantage of this approach is we are using single pass for verifying if list is palindrome.

struct  Node {     char data;     Node * pNext; }; bool IsListPalindrome(Node* head, Node* current, Node* & reverse) {     if (head)     {         head = head->pNext;         if (head)             head = head->pNext;         else         {             reverse = current->pNext;             return true;         }         if (IsListPalindrome(head, current->pNext, reverse))         {             if (current->data == reverse->data)             {                 reverse = reverse->pNext;                 return true;             }         }         return false;     }     reverse = current;     return true; }

Cloning link list with Random node pointer

You are given a link list which contains the data, next pointer and random pointer which points any random node in the list. Your task is to clone this list.

This problem can be solved using multiple approaches.

Approach 1: Brute force approach

• Clone the new list.
• Now traverse form start each time in both list for finding  out the random nodes and update the random node.

This approach will take the O(n^2) time complexity.

 

Approach 2: Use Temporary Storage 

Simply go on creating the clone and storing the map of old pointer address to its respective new pointer address and during cloning copy the random pointer address as is in the new list.Let's say pHead is pointer to old list head and pNewHead is pointer to new list, then the map will contain key as pHead and value will be pNewHead. Also pNewHead->pRandom = pHead->pRandom.

Now once new list is ready, traverse it from head again and replace each random pointer with its respective new random pointer by look up in the map.  

This way with the temporary storage of map we can clone the list as shown in below code.

struct RandomNode {     int data;     RandomNode * pNext;     RandomNode * pRandom;     RandomNode(int value) : data(value), pNext( NULL), pRandom( NULL)     {        } }; typedef  map<RandomNode *, RandomNode *> RandNodeMap; RandomNode *  CloneListUsingMap(RandomNode * pHead) {     if (pHead)     {         RandNodeMap nodeMap;         RandomNode * pTemp = pHead;         RandomNode * pNewHead = new RandomNode(pTemp->data);         pNewHead->pRandom = pTemp->pRandom;                RandomNode * pNewTemp = pNewHead;         nodeMap.insert(make_pair(pTemp, pNewTemp));                pTemp = pTemp->pNext;         while (pTemp)         {             RandomNode * pClone = new RandomNode(pTemp->data);             pClone->pRandom = pTemp->pRandom;             nodeMap.insert(make_pair(pTemp, pClone));             pNewTemp->pNext = pClone;                    pNewTemp = pNewTemp->pNext;             pTemp = pTemp->pNext;         }         pNewTemp = pNewHead;         while (pNewTemp)         {             RandNodeMap::const_iterator kit =  nodeMap.find(pNewTemp->pRandom);             pNewTemp->pRandom = kit->second;             pNewTemp = pNewTemp->pNext;         }         return pNewHead;     }     return NULL; }

The issue with the above solution is that we require the temporary storage for storing the addresses in the map.

Approach 3: Modify the existing list temporary

If we want to avoid the temporary storage, we can do that just by modifying the existing list. 
We will create the new list in the same fashion as created above. Means copy the random node address as is in the clone node random address location.
Also during creating the cloned list, attache every cloned node will be the next node of existing node.  Now for updating the random node we have to visit just the next node of the random node.
Once random nodes are updated separate the two lists.
  

RandomNode * CloneList(RandomNode * pHead) {     if (pHead)     {         RandomNode * pNewHead = new RandomNode(pHead->data);         RandomNode * pNew = pNewHead;         pNewHead->pRandom = pHead->pRandom;         RandomNode * orgList = pHead->pNext;         pHead->pNext = pNewHead;         pNewHead->pNext = orgList;         while (orgList)         {             //Create new node             RandomNode * nextNode = new RandomNode(orgList->data);             nextNode->pRandom = orgList->pRandom;                //Current list next will be new node next             nextNode->pNext = orgList->pNext;             RandomNode * tempNode = orgList;             orgList = orgList->pNext;                        //Insert it to existing list             tempNode->pNext = nextNode;         }                //Now update the random nodes of new list         pNew = pNewHead;         while (pNew)         {             pNew->pRandom = pNew->pRandom->pNext;             pNew = pNew->pNext;             if (pNew)                 pNew = pNew->pNext;             else                 break;         }         //Break entire list in to original list and cloned list         orgList = pHead;         pNew = pNewHead;         while (pNew)         {             orgList->pNext = pNew->pNext;             orgList = orgList->pNext;             if (orgList)                 pNew->pNext = orgList->pNext;             else             {                 pNew->pNext = NULL;                 break;             }             pNew = pNew->pNext;         }         return pNewHead;     }     return NULL; }

This technique just requires total three iterations of the list.

Swaping kth node from start and kth node from end from the singly link list

In order to  swap the linked list nodes you will require the previous nodes of the nodes to be swapped so that you can maintain the list.
 
We already know how to find the kth node from the end of the singly link list. We will first search for the kth node from the start and its previous node. Then we will find out the kth node from the end and its previous node. 

Then swapping these nodes will be a easy task.

//Code returns the head of the modified list. Node * SwapKthNodes(Node * pHead, int nKth) {     if (pHead)     {         Node * pKth = pHead;         Node * pKthPrev = NULL;         int i = 1;         while (pKth && i < nKth)         {             i++;             pKthPrev = pKth;             pKth = pKth->pNext;         }         //Didn't find the kth element         if (!pKth)             return pHead;         Node * temp = pKth;         Node * pKthFromEnd = pHead;         Node * pKthPrevFromEnd = NULL;         //Searching the Kth node from end         while (temp->pNext)         {             pKthPrevFromEnd = pKthFromEnd;             pKthFromEnd = pKthFromEnd->pNext;             temp = temp->pNext;         }         if (pKthFromEnd == pKth)             return pHead;         //kthpos == 1         if (!pKthPrev)         {             pKthPrevFromEnd->pNext = pHead;             Node * pTemp = pHead->pNext;             pHead->pNext = pKthFromEnd->pNext;             pKthFromEnd->pNext = pTemp;             return pKthFromEnd;         }         //KthFrom end might be the first node         if (!pKthPrevFromEnd)         {             Node * pTemp = pKthFromEnd->pNext;             pKthFromEnd->pNext = pKth->pNext;             pKth->pNext = pTemp;             pKthPrev->pNext = pKthFromEnd;             return pKth;         }         pKthPrevFromEnd->pNext = pKth;         Node * pTemp = pKth->pNext;         pKthPrev->pNext = pKthFromEnd;         Node * pTemp2 = pKthFromEnd->pNext;         pKthFromEnd->pNext = pTemp;         pKth->pNext = pTemp2;         return pHead;     }     return NULL; }

Find kth node from end in the singly linked list

You can not traverse the liked list backward unless you have stored it on the stack or at some temporary storage. So if you want to find the kth node from the end without using the temporary storage you will have to adopt different technique.

Consider a link list : 1-> 3 -> 9 -> 23 -> 14 ->NULL

Now 23 is the second last element in the list. To find this element we will use the temp linked list pointer. We will increment that pointer so that it will point to kth position from head. Once the temp pointer is pointing to kth node from head, now increment head and the temp pointer till the temp pointer points to last node of the list.  

This ways the the head will point to the kth node from the end. Code below usages the similar technique.

struct Node {     int data;     Node * pNext; }; Node * FindKthNodeFromEnd(Node * pHead, int kthPos) {     if (pHead)     {         Node * pTemp = pHead;         int i = 1;         while (i < kthPos && pTemp)         {             pTemp = pTemp->pNext;             i++;         }         if (pTemp)         {             while (pTemp->pNext)             {                 pHead = pHead->pNext;                 pTemp = pTemp->pNext;             }             return pHead;         }     }     return NULL; }

Reversing circular singley link list

In last post we have see how to reverse the single link list. We had used the iterative method to reverse the list.
Consider that you have a circular list as shown below.

Now you have to reverse the list and break the circle.
Now you can use same approach of finding out the loop in the list as discussed in the previous post. Then reverse the list recursively. 

One thing to note here is that once you find out that there is loop in the list then find out the last node of the list and then you will have to break the loop.

void ReverseCircularSinglyList(Node *pHead, Node *pHeadNext, Node * pFar, Node * pOrgHead, bool & bFoundLoop, Node * & pNewHead) {     if (pHead)     {         if (pHead->pNext == NULL)             pNewHead = pHead;         if (!bFoundLoop)         {             Node * pTemp = pHead ->pNext;             if (pFar)                 pFar = pFar->pNext;             else                 bFoundLoop = true;             if (pFar)                 pFar = pFar -> pNext;             else                 bFoundLoop = true;             if (pFar == pTemp)             {                 bFoundLoop = true;                 //found the circle                 //Now search the starting point of the circle.                 pTemp = NULL;                 while (pOrgHead != pFar)                 {                     pTemp = pFar;                     pOrgHead = pOrgHead->pNext;                     pFar = pFar -> pNext;                 }                 pTemp->pNext = NULL;             }         }         ReverseCircularSinglyList(pHead->pNext, pHead, pFar, pOrgHead, bFoundLoop, pNewHead);         pHead->pNext = pHeadNext;     } } Node * ReverseCircularSLL(Node * pHead) {     Node * pNewHead = NULL;     bool bFoundLoop = false;     ReverseCircularSinglyList(pHead, NULL, pHead, pHead, bFoundLoop, pNewHead);     return pNewHead; }

Detecting start of the loop in circular singly linked list

Consider a single linked list as below which has a loop at node 5.

As discussed in the last post we can detect if there is loop present in the list or not with use of the two pointers. To find out the start of the loop we will have to follow the same strategy. 

As we are traversing some x nodes before starting the loop hence the far and near pointer will meet at x nodes less location in the loop. If we traverse x nodes from start and x nodes from where the two pointers meet we can detect the start of the loop. 

The code below uses the same technique discussed above to detect the start of the loop in circular single linked list.

struct Node {     int data;     Node * pNext; }; Node * IsListCircular(Node * pHead) {     Node* pFar = pHead;     while (pHead != NULL && pFar !=NULL)     {         pFar = pFar->pNext;         if (pFar)             pFar = pFar->pNext;         else             return NULL;         pHead = pHead->pNext;         if (pFar == pHead)         {             return pFar;         }     }     return NULL; } Node * FindStartOfLoop(Node *pHead) {     Node * pTemp = IsListCircular(pHead);     if (pTemp)     {         while (pTemp != pHead)         {             pHead = pHead->pNext;             pTemp = pTemp->pNext;         }         return pHead;     }     return NULL; }

The function FindStartOfLoop will return the address of the start node of the loop else will return NULL.

Detecting loop in singly linked list

To detect loop in the circular singly linked list you will need two pointers. One near pointer and one far pointer.

Far pointer you will increment by two nodes where as near pointer you will increment by one so that if there is loop in the link list at some point both pointer will point to the same node. 

The code uses the similar technique.

struct Node {     int data;     Node * pNext; }; bool IsListCircular(Node * pHead) {     Node* pFar = pHead;     bool bHasLoop = false;     while (pHead != NULL)     {         if (pFar)             pFar = pFar->pNext;         else             break;         if (pFar)             pFar = pFar->pNext;         else             break;         pHead = pHead->pNext;         if (pFar == pHead)         {             bHasLoop = true;             break;         }     }     return bHasLoop; }

Reversing singly Link List

Consider you have a single link list as below:

4 -> 8 -> 1 -> NULL

and you want to reverse this list as

1 -> 8 -> 4 -> NULL

In order to reverse the list we have to make the next pointer of your node to point to earlier element in the list as below.

Original List:

4 -> 8 -> 1 -> NULL

Reversed List:

NULL <- 4 <- 8 <- 1

Now how can we make this happen. Remove one element at a time from the original list and put it to new list at the beginning as shown below.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

4 ->NULL     &  8 -> 1 -> NULL

Here we are not allocating any memory using new for new list, we have just dis-joined it from original list, follow same steps till end and you are done.

Original List:

4 -> 8 -> 1 -> NULL

New two lists:

8 -> 4 ->NULL     &  1 -> NULL

Original List:

4 -> 8 -> 1 -> NULL

New lists:

1 -> 8 -> 4 ->NULL

Following is the code for the above mentioned :

Node * ReverseList(Node * pHead) {     if (pHead)     {         Node * pLastNode = NULL;         while (pHead)         {             Node * pTemp = pHead->pNext;             pHead->pNext = pLastNode;             pLastNode = pHead;             pHead = pTemp;         }         return pLastNode;     }     return NULL; }

Here Node is struct of type: 

struct Node

{ 

    int data;  //This can be any data type

    Node * Next; 

};

Finding Middle node of the singly link list with recursion

You could find middle of the single linked list in multiple ways :

1. Simple traverse whole list once to count number of nodes in the list, then again traverse till mid element.
2. Use two list pointers, in one pass increment first list pointer by two nodes and second list pointer by one node, this way when first list pointer will reach to end of list our second pointer will be pointing to the middle of the list.
3. Use recursion to find mid.

Here we will discuss how  to reach till the mid using recursion:

To find mid you will require two things, one number elements and second how many elements we have traversed. This can be achieved using two variables one will keep track of at which element we are and one will count number of nodes till end.

int FindMid(Node * head, int nNumberOfNode = 0)

{

      if( NULL == head )

      {

            return 0;

      }

      ++ nNumberOfNode;

      int nNodeBackTraverced = FindMid(head->next, nNumberOfNode);

      if( (nNodeBackTraverced == (nNumberOfNode - 1)) || (nNodeBackTraverced  == nNumberOfNode) )

            cout << "Mid Node data: " << head->data << endl;

      return ++nNodeBackTraverced;

}

The or condition in the if will take care of both, Odd number of nodes as well as even number of nodes.

Add node at the end of linked list

Given a singly linked list and node to insert, insert given node at the end of link list.

Below is the code to add node at the end of the linked list:

Here node is of form:

struct Node {
    int data;
    Node * next;
};

Node* AddAtEnd(Node* head, int value)

{

if(head == NULL)

{

head = new Node;

head->next=NULL;

head->data= value;

return head;     

}

Node* node = head;

while( node->next!=NULL)

node = node->next;

Node* tmp = new Node;

tmp->next= NULL;

tmp->data=value;

node->next = tmp;

return head;

}