Рубрики

Учитывая связанный список отрезков, удалите средние точки

Дан связанный список координат, где соседние точки образуют вертикальную линию или горизонтальную линию. Удалите точки из связанного списка, которые находятся в середине горизонтальной или вертикальной линии.

Примеры:

Input:  (0,10)->(1,10)->(5,10)->(7,10)
                                  |
                                (7,5)->(20,5)->(40,5)
Output: Linked List should be changed to following
        (0,10)->(7,10)
                  |
                (7,5)->(40,5) 
The given linked list represents a horizontal line from (0,10) 
to (7, 10) followed by a vertical line from (7, 10) to (7, 5), 
followed by a horizontal line from (7, 5) to (40, 5).

Input:     (2,3)->(4,3)->(6,3)->(10,3)->(12,3)
Output: Linked List should be changed to following
    (2,3)->(12,3) 
There is only one vertical line, so all middle points are removed.

Источник: Microsoft Интервью Опыт

Идея состоит в том, чтобы отслеживать текущий узел, следующий узел и следующий следующий узел. Хотя следующий узел такой же, как следующий-следующий узел, продолжайте удалять следующий узел. В этой полной процедуре нам нужно следить за смещением указателей и проверкой значений NULL.

Ниже приведены реализации вышеуказанной идеи.

C ++

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

using namespace std; 

  
// Узел имеет 3 поля, включая x, y
// координаты и указатель
// к следующему узлу

class Node 

    public:

    int x, y; 

    Node *next; 

}; 

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

void push(Node ** head_ref, int x,int y) 

    Node* new_node =new Node();

    new_node->x = x; 

    new_node->y = y; 

    new_node->next = (*head_ref); 

    (*head_ref) = new_node; 

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

void printList(Node *head) 

    Node *temp = head; 

    while (temp != NULL) 

    

        cout << "(" << temp->x << "," << temp->y << ")-> "

        temp = temp->next; 

    

    cout<<endl;

  

  
// Утилита для удаления Next из связанного списка
// и связываем узлы после него с головой

void deleteNode(Node *head, Node *Next) 

    head->next = Next->next; 

    Next->next = NULL; 

    free(Next); 

  
// Эта функция удаляет средние узлы в последовательности
// горизонтальные и вертикальные отрезки, представленные
// связанный список.
Node* deleteMiddle(Node *head) 

    // Если только один узел или нет узла ... Вернуться назад

    if (head == NULL || head->next == NULL || 

                    head->next->next == NULL) 

        return head; 

  

    Node* Next = head->next; 

    Node *NextNext = Next->next ; 

  

    // Проверяем, является ли это вертикальной или горизонтальной линией

    if (head->x == Next->x) 

    

        // Находим средние узлы с одинаковым значением x и удаляем их

        while (NextNext != NULL && Next->x == NextNext->x) 

        

            deleteNode(head, Next); 

  

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

            Next = NextNext; 

            NextNext = NextNext->next; 

        

    

    else if (head->y==Next->y) // Если горизонтальная линия

    

        // Находим средние узлы с одинаковым значением y и удаляем их

        while (NextNext != NULL && Next->y == NextNext->y) 

        

            deleteNode(head, Next); 

  

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

            Next = NextNext; 

            NextNext = NextNext->next; 

        

    

    else // Соседние точки должны иметь одинаковый x или одинаковый y

    

        puts("Given linked list is not valid"); 

        return NULL; 

    

  

    // Повтор для следующего сегмента

    deleteMiddle(head->next); 

  

    return head; 

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

int main() 

    Node *head = NULL; 

  

    push(&head, 40,5); 

    push(&head, 20,5); 

    push(&head, 10,5); 

    push(&head, 10,8); 

    push(&head, 10,10); 

    push(&head, 3,10); 

    push(&head, 1,10); 

    push(&head, 0,10); 

    cout << "Given Linked List: \n"

    printList(head); 

  

    if (deleteMiddle(head) != NULL); 

    

        cout << "Modified Linked List: \n"

        printList(head); 

    

    return 0; 

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

С

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

  
// Узел имеет 3 поля, включая координаты x, y и указатель
// к следующему узлу

struct Node

{

    int x, y;

    struct Node *next;

};

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

void push(struct Node ** head_ref, int x,int y)

{

    struct Node* new_node = 

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

    new_node->x  = x;

    new_node->y  = y;

    new_node->next = (*head_ref);

    (*head_ref)  = new_node;

}

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

void printList(struct Node *head)

{

    struct Node *temp = head;

    while (temp != NULL)

    {

        printf("(%d,%d)-> ", temp->x,temp->y);

        temp = temp->next;

    }

    printf("\n");

  
}

  
// Утилита для удаления Next из связанного списка
// и связываем узлы после него с головой

void deleteNode(struct Node *head, struct Node *Next)

{

    head->next = Next->next;

    Next->next = NULL;

    free(Next);

}

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

struct Node* deleteMiddle(struct Node *head)

{

    // Если только один узел или нет узла ... Вернуться назад

    if (head==NULL || head->next ==NULL || head->next->next==NULL)

        return head;

  

    struct Node* Next = head->next;

    struct Node *NextNext = Next->next ;

  

    // Проверяем, является ли это вертикальной или горизонтальной линией

    if (head->x == Next->x)

    {

        // Находим средние узлы с одинаковым значением x и удаляем их

        while (NextNext !=NULL && Next->x==NextNext->x)

        {

            deleteNode(head, Next);

  

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

            Next = NextNext;

            NextNext = NextNext->next;

        }

    }

    else if (head->y==Next->y) // Если горизонтальная линия

    {

        // Находим средние узлы с одинаковым значением y и удаляем их

        while (NextNext !=NULL && Next->y==NextNext->y)

        {

            deleteNode(head, Next);

  

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

            Next = NextNext;

            NextNext = NextNext->next;

        }

    }

    else  // Соседние точки должны иметь одинаковый x или одинаковый y

    {

        puts("Given linked list is not valid");

        return NULL;

    }

  

    // Повтор для следующего сегмента

    deleteMiddle(head->next);

  

    return head;

}

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

int main()

{

    struct Node *head = NULL;

  

    push(&head, 40,5);

    push(&head, 20,5);

    push(&head, 10,5);

    push(&head, 10,8);

    push(&head, 10,10);

    push(&head, 3,10);

    push(&head, 1,10);

    push(&head, 0,10);

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

    printList(head);

  

    if (deleteMiddle(head) != NULL);

    {

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

        printList(head);

    }

    return 0;

}

Джава

// Java-программа для удаления средних точек в связанном списке
// отрезки,

class LinkedList

{

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

  

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

    class Node

    {

        int x,y;

        Node next;

        Node(int x, int y)

        {

            this.x = x;

            this.y = y;

            next = null;

        }

    }

  

    // Эта функция удаляет средние узлы в последовательности

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

    // по связанному списку.

    Node deleteMiddle()

    {

        // Если только один узел или нет узла ... Вернуться назад

        if (head == null || head.next == null ||

            head.next.next == null)

            return head;

  

        Node Next = head.next;

        Node NextNext = Next.next;

  

        // проверяем, является ли это вертикальной или горизонтальной линией

        if (head.x == Next.x)

        {

            // Найти средние узлы с тем же значением, что и x, и

            // удаляем их.

            while (NextNext != null && Next.x == NextNext.x)

            {

                head.next = Next.next;

                Next.next = null;

  

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

                Next = NextNext;

                NextNext = NextNext.next;

            }

        }

  

        // если горизонтальный

        else if (head.y == Next.y)

        {

            // найти средние узлы с тем же значением, что и y, и

            // удаляем их

            while (NextNext != null && Next.y == NextNext.y)

            {

                head.next = Next.next;

                Next.next = null;

  

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

                Next = NextNext;

                NextNext = NextNext.next;

            }

        }

  

        // Соседние точки должны иметь одинаковые x или одинаковые y

        else

        {

            System.out.println("Given list is not valid");

            return null;

        }

  

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

  

        // временно сохраняем голову и перемещаем голову вперед.

        Node temp = head;

        head = head.next;

  

        // вызываем deleteMiddle () для следующего сегмента

        this.deleteMiddle();

  

        // восстановить голову

        head = temp;

  

        // вернуть голову

        return head;

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int x, int y)

    {

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

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

        Node new_node = new Node(x,y);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

  

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

            System.out.print("("+temp.x+","+temp.y+")->");

            temp = temp.next;

        }

        System.out.println();

    }

  

  

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

    public static void main(String args[])

    {

        LinkedList llist = new LinkedList();

  

        llist.push(40,5);

        llist.push(20,5);

        llist.push(10,5);

        llist.push(10,8);

        llist.push(10,10);

        llist.push(3,10);

        llist.push(1,10);

        llist.push(0,10);

  

        System.out.println("Given list");

        llist.printList();

  

        if (llist.deleteMiddle() != null)

        {

            System.out.println("Modified Linked List is");

            llist.printList();

        }

    }

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

питон

# Программа Python для удаления средних точек в связанном списке
# отрезки,

class LinkedList(object):

    def __init__(self):

        self.head = None

  

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

    class Node(object):

        def __init__(self, x, y):

            self.x = x

            self.y = y

            self.next = None

  

    # Эта функция удаляет средние узлы в последовательности

    # представлены горизонтальные и вертикальные отрезки

    # по связанному списку.

    def deleteMiddle(self):

        # Если только один узел или нет узла ... Вернуться назад

        if self.head == None or self.head.next == None or self.head.next.next == None:

            return self.head

        Next = self.head.next

        NextNext = Next.next

        # проверить, является ли это вертикальной или горизонтальной линией

        if self.head.x == Next.x:

            # Найти средние узлы с тем же значением, что и x, и

            # удали их.

            while NextNext != None and Next.x == NextNext.x:

                self.head.next = Next.next

                Next.next = None

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

                Next = NextNext

                NextNext = NextNext.next

        elif self.head.y == Next.y:

            # найти средние узлы с тем же значением, что и y, и

            # удалить их

            while NextNext != None and Next.y == NextNext.y:

                self.head.next = Next.next

                Next.next = None

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

                Next = NextNext

                NextNext = NextNext.next

        else:

            # Соседние точки должны иметь одинаковые x или одинаковые y

            print "Given list is not valid"

            return None

        # повторить для другого сегмента

        # временно удерживайте голову и двигайте головой вперед.

        temp = self.head

        self.head = self.head.next

        # вызовите deleteMiddle () для следующего сегмента

        self.deleteMiddle()

        # восстановить голову

        self.head = temp

        # вернуть голову

        return self.head

  

    # Дана ссылка (указатель на указатель) на голову

    # списка и типа int, нажмите новый узел на передней панели

    № списка.

    def push(self, x, y):

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

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

        new_node = self.Node(x, y)

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

        new_node.next = self.head

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

        self.head = new_node

  

    def printList(self):

        temp = self.head

        while temp != None:

            print "(" + str(temp.x) + "," + str(temp.y) + ")->",

            temp = temp.next

        print ''

  
# Драйверная программа

llist = LinkedList()

llist.push(40,5)

llist.push(20,5)

llist.push(10,5)

llist.push(10,8)

llist.push(10,10)

llist.push(3,10)

llist.push(1,10)

llist.push(0,10)

  

print "Given list"

llist.printList()

  

if llist.deleteMiddle() != None:

    print "Modified Linked List is"

    llist.printList()

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

C #

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

using System;

  

public class LinkedList

{

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

  

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

    class Node

    {

        public int x,y;

        public Node next;

        public Node(int x, int y)

        {

            this.x = x;

            this.y = y;

            next = null;

        }

    }

  

    // Эта функция удаляет середину

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

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

    // по связанному списку.

    Node deleteMiddle()

    {

        // Если только один узел или нет узла ... Вернуться назад

        if (head == null || head.next == null ||

            head.next.next == null)

            return head;

  

        Node Next = head.next;

        Node NextNext = Next.next;

  

        // проверяем, является ли это вертикальной или горизонтальной линией

        if (head.x == Next.x)

        {

            // Находим средние узлы с одинаковыми

            // значение как х и удалить их.

            while (NextNext != null && 

                    Next.x == NextNext.x)

            {

                head.next = Next.next;

                Next.next = null;

  

                // Обновляем NextNext для

                // следующая итерация

                Next = NextNext;

                NextNext = NextNext.next;

            }

        }

  

        // если горизонтальный

        else if (head.y == Next.y)

        {

            // найти средние узлы с таким же

            // ценим как у и удаляем их

            while (NextNext != null && Next.y == NextNext.y)

            {

                head.next = Next.next;

                Next.next = null;

  

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

                Next = NextNext;

                NextNext = NextNext.next;

            }

        }

  

        // Соседние точки должны иметь одинаковые x или одинаковые y

        else

        {

            Console.WriteLine("Given list is not valid");

            return null;

        }

  

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

  

        // временно сохраняем

        // голова и движение головой вперед.

        Node temp = head;

        head = head.next;

  

        // вызываем deleteMiddle () для следующего сегмента

        this.deleteMiddle();

  

        // восстановить голову

        head = temp;

  

        // вернуть голову

        return head;

    }

  

    / * Дана ссылка (указатель на указатель) на голову

        списка и int, нажмите новый узел на передней панели

        из списка. * /

    void push(int x, int y)

    {

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

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

        Node new_node = new Node(x,y);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

  

    void printList()

    {

        Node temp = head;

        while (temp != null)

        {

            Console.Write("("+temp.x + "," + temp.y + ")->");

            temp = temp.next;

        }

        Console.WriteLine();

    }

  

  

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

    public static void Main(String []args)

    {

        LinkedList llist = new LinkedList();

  

        llist.push(40,5);

        llist.push(20,5);

        llist.push(10,5);

        llist.push(10,8);

        llist.push(10,10);

        llist.push(3,10);

        llist.push(1,10);

        llist.push(0,10);

  

        Console.WriteLine("Given list");

        llist.printList();

  

        if (llist.deleteMiddle() != null)

        {

            Console.WriteLine("Modified Linked List is");

            llist.printList();

        }

    }

}

  
// Этот код предоставлен Rajput-Ji


Выход:

Given Linked List:
(0,10)-> (1,10)-> (3,10)-> (10,10)-> (10,8)-> (10,5)-> (20,5)-> (40,5)->
Modified Linked List:
(0,10)-> (10,10)-> (10,5)-> (40,5)-> 

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

Упражнение:
Приведенный выше код является рекурсивным, напишите итерационный код для той же задачи. Пожалуйста, смотрите ниже для решения.

Итеративный подход к удалению средних точек в связанном списке линейных сегментов

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

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

Учитывая связанный список отрезков, удалите средние точки

0.00 (0%) 0 votes