Reverse a linked list in place

Reverse a linked list in place with O(n) time complexity and O(1) space complexity

Hint: Start from the head, store the prev node, move one pointer further, and make it point to prev. Complete solution can be found in the method Reverse() in the page

Find the longest two words those don’t share any characters

Given an array of words (i.e. [“apple”, “paris”, “boar”, “cat”, “tree”, “mango”]), find the max value of length(s) * length(t), where s and t are words from the array. The catch here is that the two words cannot share any characters. Assume that there are many words in the array (N words) and average length of word is M. Answer for the example above is “tree” and “mango” and the result is 4 * 5 = 20.

Hint: Hash each word, compare the hashes and get the max. You can find the solution here

Convert a tree to doubly linked list

Question: Perform a level order traversal of a binary tree. Convert the tree into doubly linked list (order of the elements should be level ordered). No extra space used and it is fine to destroy the tree.

Hint: Use a Queue, insert the children of each child into the queue. Remove the element from the queue and keep doing this until queue is empty.

Solution: Insert root’s lchild and rchild and make root’s lchild to nullptr and rchild to to the lchild. Keep doing this until queue is empty.

The implementation for this is in the page Binary tree in the method TreeToDoublyLinkedList


Deep copy a linked list with random pointer

Question:Given a linked list which has a next pointer pointing to the next element in the list and a random pointer pointing to the random element in the list. Implement a method to deep copy this linked list such that the random pointer still copies to the same node in the new list.
1. Create a copy of each node and insert the element next to the original node, iterate through the list.
2. Now the new list has 2N elements (assuming original one has N elements). Then assign the random pointer’s next node to the copied node’s random pointer. Iterate through the list.
3. Now break the list in two lists, original and new.

This logic is implemented in the method DeepCopy in the page.

Find the existence of a loop in a linked list

Question: Find if given linked list has a loop or not. If a list has a loop, then you will never stop traversing the list and visit the same set of elements again and again. For example,
1->2->3->4->5 in the list, 5 should point to NULL. However if 5 points to 3 then it has a loop 3->4->5->3->4->5->3….

Answer: Take two pointers temp1 and temp2. Advance temp1 by one element at a time and temp2 by two elements at a time and keep doing this until temp1 / temp2 is null or temp1 and temp2 pointing to the same element. If it is later case then there is a loop, otherwise there is no loop/

The code for this is defined in the method DetectLoop in the page.

Find the Kth element from the end in a linked list

Question: Given a linked list, find the kth element from the end of the list.
Answer: Take two pointers temp1 and temp2, assign both of them to head. Move one pointer (say temp1) K times so that the distance between temp1 and temp2 is k.
Now start moving both the pointers until temp1 reach the end of the list. Now temp2 points to the kth element from the end of the list.

For source code see GetKthElementFromEnd method in the page.