算法:将所有出现的元素移动到链表的结尾

2021年3月17日14:10:49 发表评论 856 次浏览

本文概述

给定一个链表和其中的一个键, 任务是将所有出现的给定键移动到链表的末尾, 同时保持所有其他元素的顺序相同。

例子:

Input  : 1 -> 2 -> 2 -> 4 -> 3
         key = 2 
Output : 1 -> 4 -> 3 -> 2 -> 2

Input  : 6 -> 6 -> 7 -> 6 -> 3 -> 10
         key = 6
Output : 7 -> 3 -> 10 -> 6 -> 6 -> 6

推荐:请尝试以下方法{IDE}首先, 在继续解决方案之前。

一种简单的解决方案一张一张地找到链表中给定密钥的所有出现。对于每个发现的事件, 将其插入末尾。直到所有出现的给定键都移到结尾为止。

时间复杂度:O(n2)

高效解决方案1:

是保持两个指针:

爬行

=>用于遍历整个列表的指针。

=>如果找到了密钥, 则指向发生密钥的指针。其他与pCrawl相同。

我们从链接列表的开头开始上述两个指针。我们走键只有当键没有指向钥匙。我们总是搬家爬行。所以什么时候爬行和键是不一样的, 我们必须找到一个位于爬行, 因此我们交换的数据爬行和键, 然后移动键到下一个位置。交换数据后, 循环不变式是来自键to爬行是钥匙。

下面是此方法的实现。

C ++

// C++ program to move all occurrences of a
// given key to end.
#include <bits/stdc++.h>
  
// A Linked list Node
struct Node {
     int data;
     struct Node* next;
};
  
// A urility function to create a new node.
struct Node* newNode( int x)
{
     Node* temp = new Node;
     temp->data = x;
     temp->next = NULL;
}
  
// Utility function to print the elements
// in Linked list
void printList(Node* head)
{
     struct Node* temp = head;
     while (temp != NULL) {
         printf ( "%d " , temp->data);
         temp = temp->next;
     }
     printf ( "\n" );
}
  
// Moves all occurrences of given key to
// end of linked list.
void moveToEnd(Node* head, int key)
{
     // Keeps track of locations where key
     // is present.
     struct Node* pKey = head;
  
     // Traverse list
     struct Node* pCrawl = head;
     while (pCrawl != NULL) {
         // If current pointer is not same as pointer
         // to a key location, then we must have found
         // a key in linked list. We swap data of pCrawl
         // and pKey and move pKey to next position.
         if (pCrawl != pKey && pCrawl->data != key) {
             pKey->data = pCrawl->data;
             pCrawl->data = key;
             pKey = pKey->next;
         }
  
         // Find next position where key is present
         if (pKey->data != key)
             pKey = pKey->next;
  
         // Moving to next Node
         pCrawl = pCrawl->next;
     }
}
  
// Driver code
int main()
{
     Node* head = newNode(10);
     head->next = newNode(20);
     head->next->next = newNode(10);
     head->next->next->next = newNode(30);
     head->next->next->next->next = newNode(40);
     head->next->next->next->next->next = newNode(10);
     head->next->next->next->next->next->next = newNode(60);
  
     printf ( "Before moveToEnd(), the Linked list is\n" );
     printList(head);
  
     int key = 10;
     moveToEnd(head, key);
  
     printf ( "\nAfter moveToEnd(), the Linked list is\n" );
     printList(head);
  
     return 0;
}

Java

// Java program to move all occurrences of a
// given key to end.
class GFG {
  
     // A Linked list Node
     static class Node {
         int data;
         Node next;
     }
  
     // A urility function to create a new node.
     static Node newNode( int x)
     {
         Node temp = new Node();
         temp.data = x;
         temp.next = null ;
         return temp;
     }
  
     // Utility function to print the elements
     // in Linked list
     static void printList(Node head)
     {
         Node temp = head;
         while (temp != null ) {
             System.out.printf( "%d " , temp.data);
             temp = temp.next;
         }
         System.out.printf( "\n" );
     }
  
     // Moves all occurrences of given key to
     // end of linked list.
     static void moveToEnd(Node head, int key)
     {
         // Keeps track of locations where key
         // is present.
         Node pKey = head;
  
         // Traverse list
         Node pCrawl = head;
         while (pCrawl != null ) {
             // If current pointer is not same as pointer
             // to a key location, then we must have found
             // a key in linked list. We swap data of pCrawl
             // and pKey and move pKey to next position.
             if (pCrawl != pKey && pCrawl.data != key) {
                 pKey.data = pCrawl.data;
                 pCrawl.data = key;
                 pKey = pKey.next;
             }
  
             // Find next position where key is present
             if (pKey.data != key)
                 pKey = pKey.next;
  
             // Moving to next Node
             pCrawl = pCrawl.next;
         }
     }
  
     // Driver code
     public static void main(String args[])
     {
         Node head = newNode( 10 );
         head.next = newNode( 20 );
         head.next.next = newNode( 10 );
         head.next.next.next = newNode( 30 );
         head.next.next.next.next = newNode( 40 );
         head.next.next.next.next.next = newNode( 10 );
         head.next.next.next.next.next.next = newNode( 60 );
  
         System.out.printf( "Before moveToEnd(), the Linked list is\n" );
         printList(head);
  
         int key = 10 ;
         moveToEnd(head, key);
  
         System.out.printf( "\nAfter moveToEnd(), the Linked list is\n" );
         printList(head);
     }
}
  
// This code is contributed by Arnab Kundu

python

# Python program to move all occurrences of a
# given key to end.
  
# Linked List node 
class Node: 
     def __init__( self , data): 
         self .data = data 
         self . next = None
  
# A urility function to create a new node.
def newNode(x):
  
     temp = Node( 0 )
     temp.data = x
     temp. next = None
     return temp
  
# Utility function to print the elements
# in Linked list
def printList( head):
  
     temp = head
     while (temp ! = None ) :
         print ( temp.data, end = " " )
         temp = temp. next
      
     print ()
  
# Moves all occurrences of given key to
# end of linked list.
def moveToEnd(head, key):
  
     # Keeps track of locations where key
     # is present.
     pKey = head
  
     # Traverse list
     pCrawl = head
     while (pCrawl ! = None ) :
          
         # If current pointer is not same as pointer
         # to a key location, then we must have found
         # a key in linked list. We swap data of pCrawl
         # and pKey and move pKey to next position.
         if (pCrawl ! = pKey and pCrawl.data ! = key) :
             pKey.data = pCrawl.data
             pCrawl.data = key
             pKey = pKey. next
          
         # Find next position where key is present
         if (pKey.data ! = key):
             pKey = pKey. next
  
         # Moving to next Node
         pCrawl = pCrawl. next
      
     return head
  
# Driver code
head = newNode( 10 )
head. next = newNode( 20 )
head. next . next = newNode( 10 )
head. next . next . next = newNode( 30 )
head. next . next . next . next = newNode( 40 )
head. next . next . next . next . next = newNode( 10 )
head. next . next . next . next . next . next = newNode( 60 )
  
print ( "Before moveToEnd(), the Linked list is\n" )
printList(head)
  
key = 10
head = moveToEnd(head, key)
  
print ( "\nAfter moveToEnd(), the Linked list is\n" )
printList(head)
  
# This code is contributed by Arnab Kundu

C#

// C# program to move all occurrences of a
// given key to end.
using System;
  
class GFG {
  
     // A Linked list Node
     public class Node {
         public int data;
         public Node next;
     }
  
     // A urility function to create a new node.
     static Node newNode( int x)
     {
         Node temp = new Node();
         temp.data = x;
         temp.next = null ;
         return temp;
     }
  
     // Utility function to print the elements
     // in Linked list
     static void printList(Node head)
     {
         Node temp = head;
         while (temp != null ) {
             Console.Write( "{0} " , temp.data);
             temp = temp.next;
         }
         Console.Write( "\n" );
     }
  
     // Moves all occurrences of given key to
     // end of linked list.
     static void moveToEnd(Node head, int key)
     {
         // Keeps track of locations where key
         // is present.
         Node pKey = head;
  
         // Traverse list
         Node pCrawl = head;
         while (pCrawl != null ) {
             // If current pointer is not same as pointer
             // to a key location, then we must have found
             // a key in linked list. We swap data of pCrawl
             // and pKey and move pKey to next position.
             if (pCrawl != pKey && pCrawl.data != key) {
                 pKey.data = pCrawl.data;
                 pCrawl.data = key;
                 pKey = pKey.next;
             }
  
             // Find next position where key is present
             if (pKey.data != key)
                 pKey = pKey.next;
  
             // Moving to next Node
             pCrawl = pCrawl.next;
         }
     }
  
     // Driver code
     public static void Main(String[] args)
     {
         Node head = newNode(10);
         head.next = newNode(20);
         head.next.next = newNode(10);
         head.next.next.next = newNode(30);
         head.next.next.next.next = newNode(40);
         head.next.next.next.next.next = newNode(10);
         head.next.next.next.next.next.next = newNode(60);
  
         Console.Write( "Before moveToEnd(), the Linked list is\n" );
         printList(head);
  
         int key = 10;
         moveToEnd(head, key);
  
         Console.Write( "\nAfter moveToEnd(), the Linked list is\n" );
         printList(head);
     }
}
  
// This code has been contributed by 29AjayKumar

输出如下:

Before moveToEnd(), the Linked list is
10 20 10 30 40 10 60 

After moveToEnd(), the Linked list is
20 30 40 60 10 10 10

时间复杂度:O(n)仅需要遍历list。

高效解决方案2:

1.遍历链接列表, 并在末尾指向一个指针。

2.现在, 检查密钥和node-> data, 如果它们相等, 则将节点移至last-next, 否则移至

先。

C ++

// C++ code to remove key element to end of linked list
#include<bits/stdc++.h>
using namespace std;
  
// A Linked list Node
struct Node 
{
     int data;
     struct Node* next;
};
  
// A urility function to create a new node.
struct Node* newNode( int x)
{
     Node* temp = new Node;
     temp->data = x;
     temp->next = NULL;
}
  
// Function to remove key to end
Node *keyToEnd(Node* head, int key)
{
  
     // Node to keep pointing to tail
     Node* tail = head;
     if (head == NULL) 
     {
         return NULL;
     }
     while (tail->next != NULL) 
     {
         tail = tail->next;
     }
      
     // Node to point to last of linked list
     Node* last = tail;
     Node* current = head;
     Node* prev = NULL;
      
     // Node prev2 to point to previous when head.data!=key
     Node* prev2 = NULL;
      
     // loop to perform operations to remove key to end
     while (current != tail) 
     {
         if (current->data == key && prev2 == NULL) 
         {
             prev = current;
             current = current->next;
             head = current;
             last->next = prev;
             last = last->next;
             last->next = NULL;
             prev = NULL;
         }
         else
         {
             if (current->data == key && prev2 != NULL)
             {
                 prev = current;
                 current = current->next;
                 prev2->next = current;
                 last->next = prev;
                 last = last->next;
                 last->next = NULL;
             }
             else if (current != tail) 
             {
                 prev2 = current;
                 current = current->next;
             }
         }
     }
     return head;
}
  
// Function to display linked list
void printList(Node* head) 
{
     struct Node* temp = head;
     while (temp != NULL) 
     {
         printf ( "%d " , temp->data);
         temp = temp->next;
     }
     printf ( "\n" );
}
  
  
// Driver Code
int main()
{
     Node* root = newNode(5);
     root->next = newNode(2);
     root->next->next = newNode(2);
     root->next->next->next = newNode(7);
     root->next->next->next->next = newNode(2);
     root->next->next->next->next->next = newNode(2);
     root->next->next->next->next->next->next = newNode(2);
  
     int key = 2;
     cout << "Linked List before operations :" ;
     printList(root);
     cout << "\nLinked List after operations :" ;
     root = keyToEnd(root, key);
     printList(root);
     return 0;
}
  
// This code is contributed by Rajout-Ji

Java

// Java code to remove key element to end of linked list
import java.util.*;
  
// Node class
class Node {
     int data;
     Node next;
  
     public Node( int data)
     {
         this .data = data;
         this .next = null ;
     }
}
  
class gfg {
  
     static Node root;
  
     // Function to remove key to end
     public static Node keyToEnd(Node head, int key)
     {
  
         // Node to keep pointing to tail
         Node tail = head;
  
         if (head == null ) {
             return null ;
         }
  
         while (tail.next != null ) {
             tail = tail.next;
         }
  
         // Node to point to last of linked list
         Node last = tail;
  
         Node current = head;
         Node prev = null ;
  
         // Node prev2 to point to previous when head.data!=key
         Node prev2 = null ;
  
         // loop to perform operations to remove key to end
         while (current != tail) {
             if (current.data == key && prev2 == null ) {
                 prev = current;
                 current = current.next;
                 head = current;
                 last.next = prev;
                 last = last.next;
                 last.next = null ;
                 prev = null ;
             }
             else {
                 if (current.data == key && prev2 != null ) {
                     prev = current;
                     current = current.next;
                     prev2.next = current;
                     last.next = prev;
                     last = last.next;
                     last.next = null ;
                 }
                 else if (current != tail) {
                     prev2 = current;
                     current = current.next;
                 }
             }
         }
         return head;
     }
  
     // Function to display linked list
     public static void display(Node root)
     {
         while (root != null ) {
             System.out.print(root.data + " " );
             root = root.next;
         }
     }
  
     // Driver Code
     public static void main(String args[])
     {
         root = new Node( 5 );
         root.next = new Node( 2 );
         root.next.next = new Node( 2 );
         root.next.next.next = new Node( 7 );
         root.next.next.next.next = new Node( 2 );
         root.next.next.next.next.next = new Node( 2 );
         root.next.next.next.next.next.next = new Node( 2 );
  
         int key = 2 ;
         System.out.println( "Linked List before operations :" );
         display(root);
         System.out.println( "\nLinked List after operations :" );
         root = keyToEnd(root, key);
         display(root);
     }
}

C#

// C# code to remove key
// element to end of linked list
using System;
  
// Node class
public class Node {
     public int data;
     public Node next;
  
     public Node( int data)
     {
         this .data = data;
         this .next = null ;
     }
}
  
class GFG {
  
     static Node root;
  
     // Function to remove key to end
     public static Node keyToEnd(Node head, int key)
     {
  
         // Node to keep pointing to tail
         Node tail = head;
  
         if (head == null ) {
             return null ;
         }
  
         while (tail.next != null ) {
             tail = tail.next;
         }
  
         // Node to point to last of linked list
         Node last = tail;
  
         Node current = head;
         Node prev = null ;
  
         // Node prev2 to point to
         // previous when head.data!=key
         Node prev2 = null ;
  
         // loop to perform operations
         // to remove key to end
         while (current != tail) {
             if (current.data == key && prev2 == null ) {
                 prev = current;
                 current = current.next;
                 head = current;
                 last.next = prev;
                 last = last.next;
                 last.next = null ;
                 prev = null ;
             }
             else {
                 if (current.data == key && prev2 != null ) {
                     prev = current;
                     current = current.next;
                     prev2.next = current;
                     last.next = prev;
                     last = last.next;
                     last.next = null ;
                 }
                 else if (current != tail) {
                     prev2 = current;
                     current = current.next;
                 }
             }
         }
         return head;
     }
  
     // Function to display linked list
     public static void display(Node root)
     {
         while (root != null ) {
             Console.Write(root.data + " " );
             root = root.next;
         }
     }
  
     // Driver Code
     public static void Main()
     {
         root = new Node(5);
         root.next = new Node(2);
         root.next.next = new Node(2);
         root.next.next.next = new Node(7);
         root.next.next.next.next = new Node(2);
         root.next.next.next.next.next = new Node(2);
         root.next.next.next.next.next.next = new Node(2);
  
         int key = 2;
         Console.WriteLine( "Linked List before operations :" );
         display(root);
         Console.WriteLine( "\nLinked List after operations :" );
         root = keyToEnd(root, key);
         display(root);
     }
}
  
// This code is contributed by PrinciRaj1992

输出如下:

Linked List before operations :
5 2 2 7 2 2 2 
Linked List after operations :
5 7 2 2 2 2 2

谢谢拉文德·库马尔建议这种方法。

高效解决方案3:是维护一个单独的密钥列表。我们将此键列表初始化为空。我们遍历给定的列表。对于找到的每个密钥, 我们将其从原始列表中删除, 然后插入单独的密钥列表中。最后, 我们在剩余给定列表的末尾链接关键字列表。该解决方案的时间复杂度也是O(n), 并且它只需要遍历list。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: