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 lengthiterative and recursive
     — search item – iterative and recursive
     — Nth node 
     — ** Rotate a Linked List around a given point k.
    *** Reverse –
    Code  Iterative (Video)  (take care of the last step to initialize the head again to the last node)
    Code Recursive (Video)


  2. ** Find the middle of a given linked list
    Algo: Using two pointers. 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) {
    fast_ptr = fast_ptr.next.next;
    slow_ptr = slow_ptr.next;
    }


  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(to calculate the length we could use the two pointer method like the above question).
    this + 1 is assuming the count is not 0 indexed. so the first node’s position is 1, next is 2 and so on…


  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
    Algo: 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 – GFG
    Note: node are same based on address and not the data.So compare address, not data.
    Floyd’s Cycle-Finding Algorithm:Proof
    Detect – 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 – First we detect that a loop exists in the list. Using the above method we find the node where both slow and fast pointer meets.
    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 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 –
    Algo: We don’t need to store the first and last node here. While traversing if the next node is same as the current node, then remove one of these node from the list.


  9. Remove duplicates from an unsorted linked list – 
    – hashing  – O(n) on average + O(n) – space. We will need to store the previous of each node as well in the hash.
    – 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)
    Code Gist – this code is a lot based on the logic to iterative rotate the list.
    The code on GFG is simpler though.


  11. *** Write a function to get the intersection point of two Linked Lists.
    There are two singly linked lists in a system. By some programming error the end node of one of the linked list got linked into the second list, forming a inverted Y shaped list. Write a program to get the point where two linked list merge.
    Algo:
    1. Mark the visited node (like the problem in finding loop)
    2. Use two loop (n^2)
    3. Use hashmap
    4.
     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.
    Time Complexity: O(m+n)
    Auxiliary Space: O(1)


  12. Move last element to front of a given Linked List – Write a function that moves last element to front in a given Singly Linked List. For example, if the given Linked List is 1->2->3->4->5, then the function should change the list to 5->1->2->3->4.
    Algo: Find the last and second last element and change the head and tail node.


  13. Intersection of two Sorted Linked Lists -Given two lists sorted in increasing order, create and return a new list representing the intersection of the two lists. The new list should be made with its own memory — the original lists should not be changed.  Code(line 68)
    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. GFG Link Two Linked Lists are identical when they have same data and arrangement of data is also same. For example Linked lists a (1->2->3) and b(1->2->3) are identical. . Write a function to check if the given two linked lists are identical.
    iterative solution is straight forward
    – Recursive solution is simple. Like the recursive count method
    Time Complexity: O(n) for both iterative and recursive versions. n is the length of the smaller list among a and b.


  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.
    Note: At the end if both the list are over, still there might be a carry left. So make sure to add the at the end of the new list created.


  16. ** Segregate even and odd nodes in a Linked List – Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list. Also, keep the order of even and odd numbers same.
    Algo:
    1. Get the last node pointer. Then start from the head. For each odd number move that node to the end.
    2. Amazon. 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.
    We create two new list pointer, one for even and one for odd. We start traversing the list. Depending on the value, we add the node to the even or odd list. We are not creating new nodes but just linking together the even and odd nodes. So at the end the main given list will be split into two list of even and odd nodes joined together. Then we append the odd list to the end of even list and set the end of odd list as null.   O(n) complexity.


  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 –
    Given a linked list, write a function to reverse every k nodes (where k is an input to the function).

    Example:
    Inputs:  1->2->3->4->5->6->7->8->NULL and k = 3 
    Output:  3->2->1->6->5->4->8->7->NULL. 
    
    Inputs:   1->2->3->4->5->6->7->8->NULL and k = 5
    Output:  5->4->3->2->1->8->7->6->NULL.

    Algo: The idea is to take a part of linked list of length ‘k’ and then reverse it and then take the second part of length of k.
    This can be iteratively also. find the start and end of ll of length k and reverse it. Then repeated.
    This seems more cleaner when done recursively. We use the logic to reverse the linked list. We start reversing the list for length k. Then we recursively again call the same method with the starting changed to node k+1 and then again start reversing.
    Read the code to reverse iteratively and then try to follow that logic recursively.


  22. ** Reverse alternate K nodes in a Singly Linked List – Code
    Algo: Same as above problem. Now that we need to skip the k node after the first k nodes are reversed. So reverse the first k nodes and then iteratively skip the k nodes. So we will pass the pointer to (k + k + 1)th node to the reverse method.
    k – reversed, k – skipped


  23. *** Rearrange a given linked list in-place – Given a singly linked list L0 -> L1 -> … -> Ln-1 -> Ln. Rearrange the nodes in the list so that the new formed list is : L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 …
    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 – Given a linked list and two keys in it, swap nodes for two given keys. Nodes should be swapped by changing links. Swapping data of nodes may be expensive in many situations when data contains many fields.  It may be assumed that all keys in linked list are distinct.Examples:
    Input:  10->15->12->13->20->14,  x = 12, y = 20
    Output: 10->15->20->13->12->14

    Algo: the problem is simple just need to take care of the edge case.
    – 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. 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 
    Algo:
    1. count 0, 1 and 2. Add them to a new list.
    2. Solve is like you would solve a similar array problem. Move 0 to left, 2 to right and don’t move the 1. Code


  26. **** Check if a singly linked list is palindrome –
    Algo:
    1. Use Stack.
    Time complexity of above method is O(n), but it requires O(n) extra space
    2. Reverse the List and compare to original list. Video
    Algo:  Split the linked list into two half across mid point. If there are odd number of nodes then ignore the middle node. Now reverse the second half of the list. Compare the two linked list. Code. The main focus here is to ignore the middle element.


  27. **** Given only a pointer to a node to be deleted in a singly linked list, how do you delete it? Or  Is it possible to delete a middle node in the single linked list when the only information available we have is the pointer to the node to be deleted and not the pointer to the previous node? After deletion the previous node should point to the node next to deleted node.

    Solution  or This

    You basically,  copy the data of node_to_delete.next to node_to_delete.data.  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).
    This might give rise to the issue of dangling pointer.  How ?
    Since to achieve the result, we dint’ actually the node to delete but overwrote it’s data and next pointer with the next’s node and deleted the next node. If there was some reference to that node we deleted, that pointer will be a dangling pointer. 


  28. ** Add 1 to a number represented as linked list -Number is represented in linked list such that each digit corresponds to a node in linked list. Add 1 to it. For example 1999 is represented as (1-> 9-> 9 -> 9) and adding 1 to it should change it to (2->0->0->0)
    Algo: 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. This can be done recursively or iteratively.


  30. Delete all occurrences of a given key in a linked list
    Algo: Simple. Need to take care of edge cases 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  (this is same as this/  Q16 on this page)
    Algo: Create two new head for new two ll – one each for odd and even node. Start traversing the given ll. Depending on the value in the ll, keep adding the current node either to the odd or even pointer. At the end join both these linked list. This also preserves the order of the main value.


  32. ** Delete N nodes after M nodes of a linked list – Code
    Algo: 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 –  Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists ‘a’ and ‘b’. The sublists should be made from alternating elements in the original list. So if the original list is 0->1->0->1->0->1 then one sublist should be 0->0->0 and the other should be 1->1->1.
    Algo: It’s very similar to Q16 on this page. 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 every-time 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  –
    Algo: 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.
    Basically find the first mismatch and check for any of the three cases above. if no msimatch then both are same.


  35. Point arbit pointer to greatest value right side node in a linked list  – Given singly linked list with every node having an additional “arbitrary” pointer that currently points to NULL. We need to make the “arbitrary” pointer to greatest value node in a linked list on its right side.  Code
    Algo: If we start from the end. The last node’s max will be null. Then for second last if will either be secondLast or last one. So if we proceed from the end and at each node keep find the max node’s value then we can keep updating each node. But since it’s a single ll we don’t have a way to move from end to front. So we start traversing the node recursively. The end condition will be if the node is null.
    Note: the arbitrary points to next value(which might or might not be the greater then the current node).
    We just reach the end of the list recursively after which  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. Given a singly linked list, remove all the nodes which have a greater value on right side. Code
    Algo:
    Same kind of approach as the above question does not works here. 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. The order of the first list  has to be maintained in the second list.
    Algo: Take the first node in the first list.  Search for that in the second list. If found check if the rest of the first list is present in the second list. If yes, good.
    Else start comparing the first element from first list, with the second node of the second list.
    Time Complexity : O(m*n) where m is the number of nodes in second list and n in first.


     

  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