{"id":4232,"date":"2021-08-24T12:10:04","date_gmt":"2021-08-24T12:10:04","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4232"},"modified":"2022-11-10T12:30:44","modified_gmt":"2022-11-10T12:30:44","slug":"move-all-occurrences-of-an-element-to-end-in-a-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/move-all-occurrences-of-an-element-to-end-in-a-linked-list\/","title":{"rendered":"Move all occurrences of an element to end in a linked list"},"content":{"rendered":"

\"\"<\/p>\n

In this article we will learn how to move all occurrences of an element to end in a linked list. As we all know Linked list is a linear data structure in which elements are linked using pointers and are not stored in contiguous memory locations. Let’s try to understand how to move all occurrences of an element to end in a linked list.<\/p>\n

Problem Statement<\/h3>\n

In this problem, we are given a linked list and a key in it. Our task is to move all the occurrences of the given key to the end of the linked list while maintaining the order of all other elements the same.<\/p>\n

Problem Statement Understanding<\/h3>\n

Let\u2019s try to understand how we can move all occurrences of an element to end in a linked list with help of examples.<\/p>\n

Let\u2019s say, we are given a linked list:<\/p>\n

\"\"<\/p>\n

Then according to the problem statement, we have to move all the occurrences of the key to the end of the linked list, and also we have to maintain the order of all other elements except the key same as their order in the original given linked list. So after moving all the occurrences of the key to the end, our final resultant linked list would look something like this:<\/p>\n

\"\"<\/p>\n

While forming the resultant linked list, first all the other elements except B will come in the same order as they were in the original linked list forming A\u2192C\u2192C and then all the occurrences of the B will be appended at the end of A\u2192C\u2192C forming A\u2192C\u2192C\u2192B\u2192B\u2192B.<\/p>\n

Explanation:<\/strong> In our final resultant linked list, we can see that all the occurrence of the key B has been moved to the end of the linked list, preserving the order of the rest of the elements of the list. <\/p>\n

Some other examples<\/h4>\n

Input:<\/strong><\/p>\n

\"\"<\/p>\n

Output:<\/strong> <\/p>\n

\"\"<\/p>\n

Input:<\/strong><\/p>\n

\"\"<\/p>\n

Output:<\/strong> <\/p>\n

\"\"<\/p>\n

Now I think from the above examples it is clear how we can move all occurrences of an element to end in a linked list. So next we have to think about how we can approach this problem towards a solution?<\/p>\n

Let\u2019s have a glance at the approach to move all occurrences of an element to end in a linked list.<\/p>\n

Approach 1 to move all occurrences of an element to end in a linked list<\/h3>\n

A simple approach is the brute force approach. <\/p>\n

In this approach, we will be finding every occurrence of the given key element in the list. <\/p>\n

    \n
  • For each occurrence of the given key element in the list, we move it to the end of the linked list.<\/li>\n<\/ul>\n

    This way, all occurrences of the given key element will be moved to the end of the linked list, and we will be successful in achieving our objective of moving all the occurrences of the given key to the end of the linked list.<\/p>\n

    Time Complexity:<\/strong> The worst case complexity of this brute force approach is O(N*N), where N is the total number of nodes in the linked list, as for each occurrence of the key element in the list, we take approx O(N) time for the traversal to the end of the linked list and then appending the key at the end.<\/p>\n

    Space Complexity:<\/strong> O(1), as no additional space is used.<\/p>\n

    Although we were able to achieve our objective still the time complexity was of order N2<\/sup>. So now we will try to think about how can we reduce this complexity. Is a lesser time complexity solution possible? If possible, what do we have to use to convert our above O(N2<\/sup>) solution into an efficient lesser time complexity solution?<\/p>\n

    Now in the next approach to move all occurrences of an element to end in a linked list we will see how using pointers we can reduce the complexity.<\/p>\n

    Approach 2 to move all occurrences of an element to end in a linked list<\/h3>\n

    The time complexity of the previous approach can be optimized if we make use of 2 pointers. <\/p>\n

    Let\u2019s say the 2 pointers are p1 and p2. <\/p>\n

      \n
    • p1 is the pointer to traverse the whole list one by one.<\/li>\n
    • p2 is the pointer to an occurrence of the key if a key is found, else it will be the same as p1.<\/li>\n<\/ul>\n

      The algorithm to move all occurrences of the key element to the end is explained below.<\/p>\n

      Algorithm:<\/h3>\n
        \n
      • We will start both pointers from the head of the linked list.<\/li>\n
      • We move p2 only when p2 is not pointing to a key. Furthermore, we always move p1 until p1!=NULL<\/strong>.<\/li>\n
      • So, when p1 and p2 are not the same, we must have found a key that lies before p1. Therefore, we swap p1 and p2 and move p2 to the next location.<\/li>\n
      • The loop invariant is, after swapping data, all node values from p2 to p1 are equal to key.<\/li>\n
      • Finally, when p1==NULL<\/strong> we will have our result, our linked list will have all the occurrences of the key at the end of the linked list.<\/li>\n<\/ul>\n

        Note:<\/strong> For a better understanding go through the dry run step by step using the algorithm and code to move all occurrences of an element to end in a linked list, hopefully, you will get to know better what we are doing in the algorithm.<\/p>\n

        Dry Run to move all occurrences of an element to end in a linked list<\/h3>\n

        \"\"
        \n\"\"<\/p>\n

        Code Implementation to move all occurrences of an element to end in a linked list<\/h3>\n\t\t\t\t\t\t