Linked List

List of 30 problems on linked list  – http://algorithmsandme.in/linked-list-problems/

  1. http://www.crazyforcode.com/linked-list/
  2. https://www.careercup.com/page?pid=linked-lists-interview-questions
  3. https://github.com/mission-peace/interview/wiki/LinkList
  4. Advantages over arrays
    1) Dynamic size
    2) Ease of insertion/deletion
    Drawbacks:
    1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
    2) Extra memory space for a pointer is required with each element of the list.

Questions –

  1. Linked List Basic Operation 
    insert – at head, at last, after a specific value, at a specific position
    delete – with given value, at given position, delete alternate node,
     — find length – iterative and recursive
    search item – iterative and recursive
    Nth node 
    Rotate a Linked List around a given point k.
    — Reverse – Code  Iterative (Video)   Recursive (Video)


  2. ** Middle Element – Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.
    while(fast!=null && fast.next !=null){}


  3.  ** n’th node from the end – this is same as (len – n + 1)th node from the beginning of the Linked List. So calculate the length and then use the formula.

  4. Delete a Linked List – In Java, automatic garbage collection happens, so deleting a linked list is easy. We just need to change head to null.

  5. ** Removing the last occurrence of an element in a (singly) linked list with only one traversal – Simply remember the previous entry every time you find the value you’re searching for on the traversal. When the traversal is complete, the last entry remembered will have a link to the entry to be removed, and that is sufficient to do the removal. Handle the case for head and tail properly.

  6. *** Detect and remove loop in linked list and remove it – Link Code
    Note: node are same based on address and not the data.So compare address, not data.
    Floyd’s Cycle-Finding Algorithm: – Proof
    Detect – This is the fastest method. Traverse linked list using two pointers. Move one pointer by one and other pointer by two. If these pointers meet at some node then there is a loop. If pointers do not meet then linked list doesn’t have loop.
    Remove – detect loop using the above algorithm. Now set the slow pointer to head and let the fast pointer remain unchanged. Now start checking until both the fast and slow pointer are same.  Read proof in the above link. Sweet and simple.
    while (slow.next != fast.next)  {
    slow = slow.next;
    fast = fast.next;
    }
    System.out.println(“Loop starts at: ” + fast.next.data);
    fast.next = null;
    Use Hashing:
    Traverse the list one by one and keep putting the node addresses in a Hash Table. At any point, if NULL is reached then return false and if next of current node points to any of the previously stored nodes in Hash then return true.
    Mark Visited Nodes:
    This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the linked list and keep marking visited nodes. If you see a visited node again then there is a loop. This solution works in O(n) but requires additional information with each node.


  7. Given a linked list which is sorted, how will you insert in sorted way  Code
    Two special case –
    1. if LL is empty
    2. if new node data is smaller then the node


  8. Remove duplicates from a sorted linked list  Code – Simply need to change pointer as all duplicate node will be together.

  9. Remove duplicates from an unsorted linked list – 
    – hashing  – O(n) on average + O(n) – space
    – sorting   – O(nLogn) + O(n) = O(nLogn)
    using two loop O(n^2)


  10. ** Pairwise swap elements of a given linked list (swap data, not the nodes)  – just exchange data b/w current and current.next node

  11. *** Write a function to get the intersection point of two Linked Lists.
    Mark the node as visited. This takes extra space and required changes to the
    original linked list, the approach can be easily used in other problem.
     counting the difference in node. Algo –
     Get count of the nodes in first and second list, let count be c1 and c2 and there
    diff d = abs(c1 – c2)
    Now traverse the bigger list from the first node till d nodes so that from here                onwards both the lists have equal no of nodes.
    Then we can traverse both the lists in parallel till we come across a common
    node. (Note that getting a common node is done by comparing the address of
    the nodes)
    the universal way of hashing can be used as well.


  12. Move last element to front of a given Linked List – find the last and second last. Update the head accordingly.

  13. ** Intersection of two Sorted Linked Lists – Code(line 68) – Simple. Algo
    – we need to create a new linked list of common elements
    –  traverse both the linked list. If both have common element then create a new node in the new linked list with the data.
    – if they are different advance in only one of the LL based on the value.
    – if one list exists before the second one then stop. There are no more common.


  14. Identical Linked Lists –
    iterative solution is straight forward
    – Recursive solution is simple. Like the recursive count method


  15.  *** Add two numbers represented by linked lists –
    Algo – Basically  we need to pick numbers from both the list and add it digit by digit. If the digit exceeds 10 then we take a carry, same as manual calculation.  We will have to maintain the carry onto the next addition. We keep doing this until reach the end of both the list. For each digit that we get we keep pushing it to a new list. 


  16. ** Segregate even and odd nodes in a Linked List –
    Algo:
    1. Get the last node pointer. Then start from the head. For each odd number move that node to the end.
    2. The idea is to split the linked list into two: one containing all even nodes and other containing all odd nodes. And finally attach the odd node linked list after the even node linked list. To split the Linked List, traverse the original Linked List and move all odd nodes to a separate Linked List of all odd nodes. At the end of loop, the original list will have all the even nodes and the odd node list will have all the odd nodes. To keep the ordering of all nodes same, we must insert all the odd nodes at the end of the odd node list. And to do that in constant time, we must keep track of last pointer in the odd node list.


  17. ** Union and Intersection of two Linked Lists  – Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn’t matter. Algo –
    1. Brute Force. O(mn)
    2. Use Sorting. Since these are linked list, use Merge Sort.Linearly scan both sorted lists to get the union and intersection. This step takes O(m + n) time.
    Overall, O(mLogm + nLogn)
    3. Hashing. Put all items of first linked list into hash table. Now start looking up for each element of second list in this table.
    If element is found, move that element to the intersection list.
    If element not found, move it to union list.
    When all items are over in list, add all element of table to hash table to union list.


  18. *** Find a triplet from three linked lists with sum equal to a given number – Algo –
    Brute force – the outermost loop picks an element from list a, the middle loop picks an element from b and the innermost loop picks from c. O(n^3)
    –  
    1) Sort list b in ascending order, and list c in descending order.
    2) After the b and c are sorted, one by one pick an element from list a and find the pair by traversing both b and c. depending on the sum value we will check if the we need to advance in node b or node c.
    complexity = O(n^2).


  19. *** Clone a linked list with next and random pointer     Video
    Type 1 (Method 1 described Below) ,  Type 2, Type 3
    Method 1 –  Time Complexity: O(n) Auxiliary Space: O(1)
    1) Create the copy of node 1 and insert it between node 1 & node 2 in original Linked List, create the copy of 2 and insert it between 2 & 3.. Continue in this fashion, add the copy of N after the Nth node.
    2) Now copy the arbitrary link in this fashion

         original->next->arbitrary = original->arbitrary->next;  /*TRAVERSE 
    TWO NODES*/
    

    This works because original->next is nothing but copy of original and Original->arbitrary->next is nothing but copy of arbitrary.
    3) Now restore the original and copy linked lists in this fashion in a single loop.

         original->next = original->next->next;
         copy->next = copy->next->next;
    

    4) Make sure that last element of original->next is NULL.
    Method 2 – Time Complexity: O(n) Auxiliary Space: O(n)
    The idea is to use Hashing. Below is algorithm.
    1. Traverse the original linked list and make a copy in terms of data.
    2. Make a hash map of key value pair with original linked list node and copied linked list node.
    3. Traverse the original linked list again and using the hash map adjust the next and random reference of cloned linked list nodes.


  20. *** Reverse a linked list – Code  Iterative (Video)   Recursive (Video)

  21. *** Reverse a Linked List in groups of given size – Read the code to reverse iteratively and then try to follow that logic recursively. Remember – prev and next are the key.

  22. *** Reverse alternate K nodes in a Singly Linked List – Code
    For all the reverse question – draw out the list on paper and work out the problem.


  23. *** Rearrange a given linked list in-place.
    Algo 1,  Time complexity = O(n2)1) Initialize current node as head.
    2) While next of current node is not null, do following
    a) Find the last node, remove it from end and insert it as next of current node.          b) Move current to next to next of current
    Algo 2, Time complexity = O(n)
    1) Find the middle point using tortoise and hare method.
    2) Split the linked list in two halves using found middle point in step 1.
    3) Reverse the second half.
    4) Do alternate merge of first and second halves.


  24. Swap nodes in a linked list without swapping data –
    – if both x and y are same – don’t do anything
    – find the currentX and prevX and currentY and prevY
    – if currX or  currY is null( does not exits) return
    – check if either currX or currY is head. This can be done using prevX == null or
    prevY == null. If yes then we need to change next accordingly.
    – // If x is not head of linked list
    if (prevX != null)
    prevX.next = currY;
    else //make y the new head
    head = currY;
    // If y is not head of linked list
    if (prevY != null)
    prevY.next = currX;
    else // make x the new head
    head = currX;
    // Swap next pointers
    Node temp = currX.next;
    currX.next = currY.next;
    currY.next = temp;


  25. *** Sort a linked list of 0s, 1s and 2s – count 0, 1 and 2. Add them to a new list.

  26. *** Check if a singly linked list is palindrome –
    – Use Stack
    – Reverse the List and compare to original list


  27. *** Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? Solution  or This
    You basically,  copy the data of node_to_delete.next to node_to_delete.data.  So the Then point node_to_delete.next to node_to_delete.next.next. So u basically remove node_to_delete.next from scene(garbage collector will take of that node).
    (not the previous node pointing to node_to_delete is still working).You might be asked to discuss about the dangling pointer case if the node_to_delete.next was being referred from somewhere else.


  28. ** Add 1 to a number represented as linked list – this is very similar to Add two numbers represented by linked lists . The only difference is the order. So first reverse the list. Do the old school addition with carry. Then reverse it back again.

  29. Given a linked list of co-ordinates where adjacent points either form a vertical line or a horizontal line. Delete points from the linked list which are in the middle of a horizontal or vertical line. –  Link Code
    Algo – The idea is to keep track of current node, next node and next-next node. While the next node is same as next-next node, keep deleting the next node. In this complete procedure we need to keep an eye on shifting of pointers and checking for NULL values.


  30. Delete all occurrences of a given key in a linked list – need to take care if the value exists at the head, rest the logic is straightforward.

  31. Rearrange a linked list such that all even and odd positioned nodes are together Code  Algo –
    we want to separate the old and even node. So initially I though of moving all the odd nodes to the end of the list. But then we wouldn’t know when to stop traversing the list.
    We mark the head node as even and the head.next as odd. We create a temp node which points to the start of this odd. Now we follow our initial approach. We keep shifting from even node to even node by linking them, at the same time we keep linking the all nodes together. In the end we stop at even node, then we update the tail node of even to point to the temp node we created initially, which points to the odd node. While linking even node we also linked all the odd nodes.


  32. ** Delete N nodes after M nodes of a linked list – Code We count m node initially. Store the prev node at also. Then when deleted we count n nodes. At the end of that we set the prev to the pointer to the next of last node to be deleted.

  33. Alternating split of a given Singly Linked List –  we need to create two new list here. The only thing to note is that the order is maintained(Best to clarify this from the interviewer). If we keep inserting at the end, we will have to start from the head till the last node.  Since this can be an expensive operation we save a reference to the tail node and use it everytime we need to add node to tail. Just an O(1)  for adding new node to tail.

  34. Compare two strings represented as linked lists  – Looks complicated but boils down to three simple case. 1. If both are same. 2. If 1 is bigger then the other the first one comes first lexicographically. If both have different character, then we pick up the pick character that are different and then compare.

  35. Point arbit pointer to greatest value right side node in a linked list    Code
    Note: the arbitrary points to next value(which might or might not be the greater then the current node). In the code we are not doing anything to the next node. We just reach the end of the list recursively after which I we mark the last node as maxNode for the second last node (arbitrary for last node will be null and for second last node it will always be last node). After that we start comparing the value of current node with the max and keep updating it.
    Draw out on a paper before proceeding for better understanding.
    No need to reverse the list.


  36. Delete nodes which have a greater value on right side Code
    Algo – without reversing it’s not possible in O(n). tried that but failed at this
    case:  12->10->8->11. We can keep deleting when moving forward but this case can’t be handled like that. So had to follow the approach given in link above.
    Reversing helps as when we move forward we keep a max reference and easy deletion. One observation – the final list will always be in descending order.
    So instead of deleting the one on left, we reverse and delete on right, any value that is smaller then the current value.


  37. Given two linked lists, the task is to check whether the first list is present in 2nd list or not.

     

  38. Given a sorted linked list, delete all nodes that have duplicate numbers (all occurrences), leaving only numbers that appear once in the original list. GFG.
    Algo: Nothing much to discuss here. It’s given list is sorted. Can be easily implemented in O(n) with no extra space.


  39. Given a linked list and a key in it, the task is to move all occurrences of given key to end of linked list, keeping order of all other elements same.
    Algo:
    We create a new null node. We traverse the list. Basically we will make this pointer point to the first occurence of the key in list and then keep linking this next’s item in the list to next occurence of the element. So that all  nodes of with given key are linked together. At the same time we also keep removing the key’s node link in the main list. Check the eg below.
    2  -> 3 -> 4 -> 5 -> 3 -> 6 ->7 -> null
    If we need to remove 3, the new list will be,2  ->  4 -> 5  -> 6 ->7 -> null
    N the new pointer will be 3->3->null. Now link this pointer to the end of this original list.
    The code is simple and a similar example has been coded. Not sure which question though.

 PENDING

  1. Flattening a Linked List
  2. [Pending] Select a Random Node from a Singly Linked List
      Read this for the algo here

  1. [Skip] Flatten a multilevel linked list
  2. [Skip] Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some Common nodes
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s