Рубрики

Объединить связанный список в другой связанный список на альтернативных позициях

Имея два связанных списка, вставьте узлы второго списка в первый список в альтернативных позициях первого списка.
Например, если первый список 5-> 7-> 17-> 13-> 11, а второй 12-> 10-> 2-> 4-> 6, первый список должен стать 5-> 12-> 7- > 10-> 17-> 2-> 13-> 4-> 11-> 6 и второй список должен стать пустым. Узлы второго списка должны быть вставлены только при наличии доступных позиций. Например, если первый список 1-> 2-> 3, а второй список 4-> 5-> 6-> 7-> 8, то первый список должен стать 1-> 4-> 2-> 5-> 3-> 6 и второй список до 7-> 8.

Использование дополнительного пространства не допускается (не разрешается создавать дополнительные узлы), т. Е. Вставка должна выполняться на месте. Ожидаемая сложность по времени составляет O (n), где n — количество узлов в первом списке.

Идея состоит в том, чтобы запустить цикл, пока есть свободные позиции в первом цикле, и вставить узлы второго списка, изменяя указатели. Ниже приведены реализации этого подхода.

C ++

// C ++ программа для объединения связанного списка в другой
// альтернативные позиции
#include <bits/stdc++.h>

using namespace std;

  
// узел следующего списка

class Node 

    public:

    int data; 

    Node *next; 

}; 

  
/ * Функция для вставки узла в начале * /

void push(Node ** head_ref, int new_data) 

    Node* new_node = new Node();

    new_node->data = new_data; 

    new_node->next = (*head_ref); 

    (*head_ref) = new_node; 

  
/ * Утилита для печати односвязного списка * /

void printList(Node *head) 

    Node *temp = head; 

    while (temp != NULL) 

    

        cout<<temp->data<<" "

        temp = temp->next; 

    

    cout<<endl;

  
// Основная функция, которая вставляет узлы связанного списка q в p в
// альтернативные позиции. Так как глава первого списка никогда не меняется
// и заголовок второго списка может измениться, нам нужен один указатель
// для первого списка и двойной указатель для второго списка.

void merge(Node *p, Node **q) 

    Node *p_curr = p, *q_curr = *q; 

    Node *p_next, *q_next; 

  

    // Пока есть доступные позиции в p

    while (p_curr != NULL && q_curr != NULL) 

    

        // Сохранить следующие указатели

        p_next = p_curr->next; 

        q_next = q_curr->next; 

  

        // Сделать q_curr следующим за p_curr

        q_curr->next = p_next; // Изменить следующий указатель на q_curr

        p_curr->next = q_curr; // Изменить следующий указатель на p_curr

  

        // Обновляем текущие указатели для следующей итерации

        p_curr = p_next; 

        q_curr = q_next; 

    

  

    *q = q_curr; // Обновить указатель головы второго списка

  
// Код драйвера

int main() 

    Node *p = NULL, *q = NULL; 

    push(&p, 3); 

    push(&p, 2); 

    push(&p, 1); 

    cout<<"First Linked List:\n"

    printList(p); 

  

    push(&q, 8); 

    push(&q, 7); 

    push(&q, 6); 

    push(&q, 5); 

    push(&q, 4); 

    cout<<"Second Linked List:\n"

    printList(q); 

  

    merge(p, &q); 

  

    cout<<"Modified First Linked List:\n"

    printList(p); 

  

    cout<<"Modified Second Linked List:\n"

    printList(q); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// C-программа для объединения связанного списка в другой
// альтернативные позиции
#include <stdio.h>
#include <stdlib.h>

  
// узел следующего списка

struct Node

{

    int data;

    struct Node *next;

};

  
/ * Функция для вставки узла в начале * /

void push(struct Node ** head_ref, int new_data)

{

    struct Node* new_node = 

           (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = (*head_ref);

    (*head_ref)  = new_node;

}

  
/ * Утилита для печати односвязного списка * /

void printList(struct Node *head)

{

    struct Node *temp = head;

    while (temp != NULL)

    {

        printf("%d ", temp->data);

        temp = temp->next;

    }

    printf("\n");

}

  
// Основная функция, которая вставляет узлы связанного списка q в p в
// альтернативные позиции. Так как глава первого списка никогда не меняется
// и заголовок второго списка может измениться, нам нужен один указатель
// для первого списка и двойной указатель для второго списка.

void merge(struct Node *p, struct Node **q)

{

     struct Node *p_curr = p, *q_curr = *q;

     struct Node *p_next, *q_next;

  

     // Пока есть доступные позиции в p

     while (p_curr != NULL && q_curr != NULL)

     {

         // Сохранить следующие указатели

         p_next = p_curr->next;

         q_next = q_curr->next;

  

         // Сделать q_curr следующим за p_curr

         q_curr->next = p_next;  // Изменить следующий указатель на q_curr

         p_curr->next = q_curr;  // Изменить следующий указатель на p_curr

  

         // Обновляем текущие указатели для следующей итерации

         p_curr = p_next;

         q_curr = q_next;

    }

  

    *q = q_curr; // Обновить указатель головы второго списка

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

     struct Node *p = NULL, *q = NULL;

     push(&p, 3);

     push(&p, 2);

     push(&p, 1);

     printf("First Linked List:\n");

     printList(p);

  

     push(&q, 8);

     push(&q, 7);

     push(&q, 6);

     push(&q, 5);

     push(&q, 4);

     printf("Second Linked List:\n");

     printList(q);

  

     merge(p, &q);

  

     printf("Modified First Linked List:\n");

     printList(p);

  

     printf("Modified Second Linked List:\n");

     printList(q);

  

     getchar();

     return 0;

}

Джава

// Java-программа для объединения связанного списка в другой
// альтернативные позиции

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d) {data = d; next = null; }

    }

  

    / * Вставляет новый узел в начало списка. * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

    // Основная функция, которая вставляет узлы связанного списка q в p в

    // альтернативные позиции. Так как глава первого списка никогда не меняется

    // и заголовок второго списка / может измениться, нам нужен один указатель

    // для первого списка и двойной указатель для второго списка.

    void merge(LinkedList q)

    {

        Node p_curr = head, q_curr = q.head;

        Node p_next, q_next;

  

        // Пока есть свободные позиции в p;

        while (p_curr != null && q_curr != null) {

  

            // Сохранить следующие указатели

            p_next = p_curr.next;

            q_next = q_curr.next;

  

            // сделать q_curr следующим за p_curr

            q_curr.next = p_next; // меняем следующий указатель на q_curr

            p_curr.next = q_curr; // меняем следующий указатель на p_curr

  

            // обновляем текущие указатели для следующей итерации

            p_curr = p_next;

            q_curr = q_next;

        }

        q.head = q_curr;

    }

  

    / * Функция для печати связанного списка * /

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

           System.out.print(temp.data+" ");

           temp = temp.next;

        }

        System.out.println();

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

        llist1.push(3);

        llist1.push(2);

        llist1.push(1);

  

        System.out.println("First Linked List:");

        llist1.printList();

  

        llist2.push(8);

        llist2.push(7);

        llist2.push(6);

        llist2.push(5);

        llist2.push(4);

  

        System.out.println("Second Linked List:");

  

        llist1.merge(llist2);

  

        System.out.println("Modified first linked list:");

        llist1.printList();

  

        System.out.println("Modified second linked list:");

        llist2.printList();

    }

} / * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python для объединения связанного списка в другой
# альтернативные позиции

class LinkedList(object):

    def __init__(self):

    # заголовок списка

        self.head = None

  

    # Узел связанного списка

    class Node(object):

        def __init__(self, d):

            self.data = d

            self.next = None

  

    # Вставляет новый узел в начало списка.

    def push(self, new_data):

  

        # 1 & 2: выделить узел &

        # Вставьте данные

        new_node = self.Node(new_data)

  

        # 3. Сделать следующий из нового узла в качестве головы

        new_node.next = self.head

  

        # 4. Переместите голову, чтобы указать на новый узел

        self.head = new_node

  

    # Основная функция, которая вставляет узлы связанного списка q в p в

    # альтернативные позиции. Так как глава первого списка никогда не меняется

    # и заголовок второго списка / может измениться, нам нужен один указатель

    # для первого списка и двойной указатель для второго списка.

    def merge(self, q):

        p_curr = self.head

        q_curr = q.head

  

        # Пока есть свободные позиции в р;

        while p_curr != None and q_curr != None:

  

            # Сохранить следующие указатели

            p_next = p_curr.next

            q_next = q_curr.next

  

            # сделать q_curr следующим за p_curr

            q_curr.next = p_next # изменить следующий указатель на q_curr

            p_curr.next = q_curr # изменить следующий указатель на p_curr

  

            # обновить текущие указатели для следующей итерации

            p_curr = p_next

            q_curr = q_next

        q.head = q_curr

  

    # Функция для печати связанного списка

    def printList(self):

        temp = self.head

        while temp != None:

            print str(temp.data),

            temp = temp.next

        print ''

  
# Драйверная программа для проверки вышеуказанных функций

llist1 = LinkedList()

llist2 = LinkedList()

llist1.push(3)

llist1.push(2)

llist1.push(1)

  

print "First Linked List:"

llist1.printList()

  

llist2.push(8)

llist2.push(7)

llist2.push(6)

llist2.push(5)

llist2.push(4)

  

print "Second Linked List:"

  
llist2.printList()
llist1.merge(llist2)

  

print "Modified first linked list:"

llist1.printList()

  

print "Modified second linked list:"

llist2.printList()

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # программа для объединения связанного списка в
// другой на альтернативных позициях

using System;

  

public class LinkedList 

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        {

             data = d; 

             next = null;

        

    

  

    / * Вставляет новый узел в начало списка. * /

    void push(int new_data) 

    

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data); 

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head; 

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node; 

    

  

    // Основная функция, которая вставляет узлы

    // связанного списка q в p на альтернативном

    // позиции. С начала первого списка

    // никогда не меняется и голова вторая

    // список / может измениться, нам нужен одиночный

    // указатель на первый список и двойной

    // указатель на второй список.

    void merge(LinkedList q) 

    

        Node p_curr = head, q_curr = q.head; 

        Node p_next, q_next; 

  

        // Пока есть свободные позиции в p;

        while (p_curr != null && q_curr != null)

        

  

            // Сохранить следующие указатели

            p_next = p_curr.next; 

            q_next = q_curr.next; 

  

            // сделать q_curr следующим за p_curr

            q_curr.next = p_next; // меняем следующий указатель на q_curr

            p_curr.next = q_curr; // меняем следующий указатель на p_curr

  

            // обновляем текущие указатели для следующей итерации

            p_curr = p_next; 

            q_curr = q_next; 

        

        q.head = q_curr; 

    

  

    / * Функция для печати связанного списка * /

    void printList() 

    

        Node temp = head; 

        while (temp != null

        

            Console.Write(temp.data+" "); 

            temp = temp.next; 

        

        Console.WriteLine(); 

    

  

    / * Код водителя * /

    public static void Main() 

    

        LinkedList llist1 = new LinkedList(); 

        LinkedList llist2 = new LinkedList(); 

        llist1.push(3); 

        llist1.push(2); 

        llist1.push(1); 

  

        Console.WriteLine("First Linked List:"); 

        llist1.printList(); 

  

        llist2.push(8); 

        llist2.push(7); 

        llist2.push(6); 

        llist2.push(5); 

        llist2.push(4); 

  

        Console.WriteLine("Second Linked List:"); 

  

        llist1.merge(llist2); 

  

        Console.WriteLine("Modified first linked list:"); 

        llist1.printList(); 

  

        Console.WriteLine("Modified second linked list:"); 

        llist2.printList(); 

    

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

First Linked List:
1 2 3
Second Linked List:
4 5 6 7 8
Modified First Linked List:
1 4 2 5 3 6
Modified Second Linked List:
7 8 

Эта статья предоставлена Чандрой Пракаш . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Объединить связанный список в другой связанный список на альтернативных позициях

0.00 (0%) 0 votes