При наличии связанного списка и ключа в нем задача состоит в том, чтобы переместить все вхождения данного ключа в конец связанного списка, сохраняя порядок всех остальных элементов одинаковым.
Примеры:
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 Простое решение состоит в том, чтобы один за другим найти все вхождения данного ключа в связанном списке. Для каждого найденного случая вставьте его в конце. Мы делаем это, пока все вхождения данного ключа не будут перемещены в конец.
Сложность времени: O (n 2 )
Эффективное решение 1: сохранить два указателя:
pCrawl => Указатель для обхода всего списка один за другим.
pKey => Указатель на вхождение ключа, если ключ найден. Остальное так же, как pCrawl.
Мы начинаем оба вышеуказанных указателя с заголовка связанного списка. Мы перемещаем pKey только тогда, когда pKey не указывает на клавишу. Мы всегда перемещаем pCrawl . Таким образом, когда pCrawl и pKey не совпадают, мы должны найти ключ, который находится перед pCrawl , поэтому мы меняем данные pCrawl и pKey и перемещаем pKey в следующее место. Инвариант цикла состоит в том, что после замены данных все элементы от pKey до pCrawl являются ключами.
Ниже приведена реализация этого подхода.
C ++
#include <bits/stdc++.h>
struct Node {
int data;
struct Node* next;
};
struct Node* newNode(int x)
{
Node* temp = new Node;
temp->data = x;
temp->next = NULL;
}
void printList(Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
void moveToEnd(Node* head, int key)
{
struct Node* pKey = head;
struct Node* pCrawl = head;
while (pCrawl != NULL) {
if (pCrawl != pKey && pCrawl->data != key) {
pKey->data = pCrawl->data;
pCrawl->data = key;
pKey = pKey->next;
}
if (pKey->data != key)
pKey = pKey->next;
pCrawl = pCrawl->next;
}
}
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;
}
|
Джава
class GFG {
static class Node {
int data;
Node next;
}
static Node newNode(int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
static void printList(Node head)
{
Node temp = head;
while (temp != null) {
System.out.printf("%d ", temp.data);
temp = temp.next;
}
System.out.printf("\n");
}
static void moveToEnd(Node head, int key)
{
Node pKey = head;
Node pCrawl = head;
while (pCrawl != null) {
if (pCrawl != pKey && pCrawl.data != key) {
pKey.data = pCrawl.data;
pCrawl.data = key;
pKey = pKey.next;
}
if (pKey.data != key)
pKey = pKey.next;
pCrawl = pCrawl.next;
}
}
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);
}
}
|
C #
using System;
class GFG {
public class Node {
public int data;
public Node next;
}
static Node newNode(int x)
{
Node temp = new Node();
temp.data = x;
temp.next = null;
return temp;
}
static void printList(Node head)
{
Node temp = head;
while (temp != null) {
Console.Write("{0} ", temp.data);
temp = temp.next;
}
Console.Write("\n");
}
static void moveToEnd(Node head, int key)
{
Node pKey = head;
Node pCrawl = head;
while (pCrawl != null) {
if (pCrawl != pKey && pCrawl.data != key) {
pKey.data = pCrawl.data;
pCrawl.data = key;
pKey = pKey.next;
}
if (pKey.data != key)
pKey = pKey.next;
pCrawl = pCrawl.next;
}
}
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);
}
}
|
Выход:
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) требует только одного обхода списка.
Эффективное решение 2:
1. Пройдите по связанному списку и возьмите указатель на хвост.
2. Теперь проверьте ключ и данные узла->, если они равны, переместите узел на последнюю-следующую, иначе переместите
вперед.
Джава
import java.util.*;
class Node {
int data;
Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
class gfg {
static Node root;
public static Node keyToEnd(Node head, int key)
{
Node tail = head;
if (head == null) {
return null;
}
while (tail.next != null) {
tail = tail.next;
}
Node last = tail;
Node current = head;
Node prev = null;
Node prev2 = null;
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;
}
public static void display(Node root)
{
while (root != null) {
System.out.print(root.data + " ");
root = root.next;
}
}
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 #
using System;
public class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
class GFG {
static Node root;
public static Node keyToEnd(Node head, int key)
{
Node tail = head;
if (head == null) {
return null;
}
while (tail.next != null) {
tail = tail.next;
}
Node last = tail;
Node current = head;
Node prev = null;
Node prev2 = null;
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;
}
public static void display(Node root)
{
while (root != null) {
Console.Write(root.data + " ");
root = root.next;
}
}
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);
}
}
|
Выход:
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), и для этого также требуется только один обход списка.
Эта статья предоставлена МАЖАР ИМАМ ХАН. Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.
Рекомендуемые посты:
Переместить все вхождения элемента в конец связанного списка
0.00 (0%) 0 votes