Рубрики

Напишите функцию для получения N-го узла в связанном списке

Напишите функцию GetNth (), которая принимает связанный список и целочисленный индекс и возвращает значение данных, хранящихся в узле в этой позиции индекса.

Пример:

Input:  1->10->30->14,  index = 2
Output: 30  
The node at index 2 is 30

Алгоритм:

1. Initialize count = 0
2. Loop through the link list
     a. if count is equal to the passed index then return current
         node
     b. Increment count
     c. change current to point to next of the current.

Реализация:

C ++

// C ++ программа для поиска n'th
// узел в связанном списке
#include <bits/stdc++.h>
#include <assert.h> 

using namespace std;

  
// узел списка ссылок

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * Дана ссылка (указатель на
указатель) на начало списка
и INT, нажмите новый узел на
передняя часть списка. * /

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; 

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

int GetNth(Node* head, int index) 

      

    Node* current = head; 

      

    // индекс

    // узел мы в данный момент

    // смотря на

    int count = 0; 

    while (current != NULL) 

    

        if (count == index) 

            return(current->data); 

        count++; 

        current = current->next; 

    

  

    / * если мы доберемся до этой строки,

    звонивший спрашивал

    для несуществующего элемента

    поэтому мы утверждаем неудачу * /

    assert(0);         

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

int main() 

      

    // Начнем с

    // пустой список

    Node* head = NULL; 

  

    // Используем push () для построения

    // ниже списка

    // 1-> 12-> 1-> 4-> 1

    push(&head, 1); 

    push(&head, 4); 

    push(&head, 1); 

    push(&head, 12); 

    push(&head, 1); 

  

    // Проверяем количество

    // функция

    cout << "Element at index 3 is " << GetNth(head, 3); 

    return 0;

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

С

// C программа для поиска n'th
// узел в связанном списке
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

  
// узел списка ссылок

struct Node

{

    int data;

    struct Node* next;

};

  
/ * Дана ссылка (указатель на

   указатель) на начало списка

   и INT, нажмите новый узел на

   передняя часть списка. * /

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;

}

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

int GetNth(struct Node* head, 

                  int index)

{

      

    struct Node* current = head;

      

     // индекс

     // узел мы в данный момент

     // смотря на

    int count = 0;

    while (current != NULL)

    {

        if (count == index)

            return(current->data);

        count++;

        current = current->next;

    }

  

    / * если мы доберемся до этой строки,

       звонивший спрашивал

       для несуществующего элемента

       поэтому мы утверждаем неудачу * /

    assert(0);             

}

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

int main()

{

      

    // Начнем с

    // пустой список

    struct Node* head = NULL;

  

    // Используем push () для построения

    // ниже списка

    // 1-> 12-> 1-> 4-> 1

    push(&head, 1);

    push(&head, 4);

    push(&head, 1);

    push(&head, 12);

    push(&head, 1); 

  

    // Проверяем количество

    // функция

    printf("Element at index 3 is %d"

                     GetNth(head, 3)); 

    getchar();

}

Джава

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

  

class Node

{

    int data;

    Node next;

    Node(int d)

    {

        data = d;

        next = null;

    }

}

  

class LinkedList

{

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

  

    / * Принимает индекс в качестве аргумента и возвращает данные в индексе * /

    public int GetNth(int index)

    {

        Node current = head;

        int count = 0; / * индекс узла мы

                          в настоящее время глядя на * /

        while (current != null)

        {

            if (count == index)

                return current.data;

            count++;

            current = current.next;

        }

  

        / * если мы дойдем до этой строки, вызывающая сторона спрашивала

        для несуществующего элемента, поэтому мы утверждаем неудачу * /

        assert(false);

        return 0;

    }

  

    / * Учитывая ссылку на заголовок списка и int,

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

    public void push(int new_data)

    {

  

        / * 1. выделить узел и поместить данные * /

        Node new_Node = new Node(new_data);

  

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

        new_Node.next = head;

  

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

        head = new_Node;

    }

  

    / * Сушилка для тестирования вышеуказанных функций * /

    public static void main(String[] args)

    {

        / * Начать с пустого списка * /

        LinkedList llist = new LinkedList();

  

        / * Используйте push () для построения списка ниже

           1-> 12-> 1-> 4-> 1 * /

        llist.push(1);

        llist.push(4);

        llist.push(1);

        llist.push(12);

        llist.push(1);

  

        / * Проверьте функцию подсчета * /

        System.out.println("Element at index 3 is "+llist.GetNth(3));

    }

}

питон

# Полная рабочая программа на Python для поиска n-го узла
# в связанном списке

  
# Класс узла

class Node:

    # Функция для инициализации объекта узла

    def __init__(self, data):

        self.data = data # Назначить данные

        self.next = None # Инициализировать следующий как ноль

  

  
# Класс связанного списка содержит объект Node

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

  

    # Эта функция находится в классе LinkedList. Вставляет

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

    def push(self, new_data):

  

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

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

        new_node = Node(new_data)

  

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

        new_node.next = self.head

  

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

        self.head = new_node

  

    # Возвращает данные по указанному индексу в связанном списке

    def getNth(self, index):

        current = self.head # Initialize temp

        count = 0 # Индекс текущего узла

  

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

        while (current):

            if (count == index):

                return current.data

            count += 1

            current = current.next

  

        # если мы дойдем до этой строки, звонивший спрашивал

        # для несуществующего элемента, поэтому мы утверждаем неудачу

        assert(false)

        return 0;

  
# Выполнение кода начинается здесь

if __name__=='__main__':

  

    llist = LinkedList()

  

    # Используйте push () для построения списка ниже

    # 1-> 12-> 1-> 4-> 1

    llist.push(1);

    llist.push(4);

    llist.push(1);

    llist.push(12);

    llist.push(1);

  

    n = 3

    print ("Element at index 3 is :", llist.getNth(n))

C #

// C # программа для поиска n-го узла в связанном списке

using System;

using System.Diagnostics;

  

public class Node 

    public int data; 

    public Node next; 

    public Node(int d) 

    

        data = d; 

        next = null

    

  

class LinkedList 

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

  

    / * Принимает индекс в качестве аргумента и возвращает данные в индексе * /

    public int GetNth(int index) 

    

        Node current = head; 

        int count = 0; / * индекс узла мы

                        в настоящее время глядя на * /

        while (current != null

        

            if (count == index) 

                return current.data; 

            count++; 

            current = current.next; 

        

  

        / * если мы дойдем до этой строки, вызывающая сторона спрашивала

        для несуществующего элемента, поэтому мы утверждаем неудачу * /

        Debug.Assert(false); 

        return 0; 

    

  

    / * Учитывая ссылку на заголовок списка и int,

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

    public void push(int new_data) 

    

  

        / * 1. выделить узел и поместить данные * /

        Node new_Node = new Node(new_data); 

  

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

        new_Node.next = head; 

  

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

        head = new_Node; 

    

  

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

    public static void Main(String []args) 

    

        / * Начать с пустого списка * /

        LinkedList llist = new LinkedList(); 

  

        / * Используйте push () для построения списка ниже

        1-> 12-> 1-> 4-> 1 * /

        llist.push(1); 

        llist.push(4); 

        llist.push(1); 

        llist.push(12); 

        llist.push(1); 

  

        / * Проверьте функцию подсчета * /

        Console.WriteLine("Element at index 3 is "+

                            llist.GetNth(3)); 

    

  
// Этот код предоставлен Арнабом Кунду


Выход:

Element at index 3 is 4

Сложность времени: O (n)

Метод 2 — с рекурсией
Этот метод предоставлен MY_DOOM .
Алгоритм:

Algorithm
getnth(node,n)
1. Initialize count = 1
2. if count==n
     return node->data
3. else
    return getnth(node->next,n-1)
    

Реализация:

C ++

// C программа для поиска n-го узла в связанном списке
// используя рекурсию
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node

{

    int data;

    struct Node* next;

};

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

    глава списка и INT, нажмите

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

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;

}

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

    в качестве аргументов и возврата данных по индексу * /

int GetNth(struct Node *head,int n)

{

    int count = 1;

      

    // если количество равно тоже n вернуть узел-> данные

    if(count == n)

    return head->data;

      

    // рекурсивно уменьшаем n и увеличиваем

    // голова к следующему указателю

    return GetNth(head->next, n-1); 

}

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

int main()

{

     / * Начнем с пустого списка * /

    struct Node* head = NULL;

     

    / * Используйте push () для построения списка ниже

     1-> 12-> 1-> 4-> 1 * /

    push(&head, 1);

    push(&head, 4);

    push(&head, 1);

    push(&head, 12);

    push(&head, 1);  

     

    / * Проверьте функцию подсчета * /

    printf("Element at index 3 is %d", GetNth(head, 3));  

    getchar();

}

Джава

// Java-программа для поиска n-го узла в связанном списке
// используя рекурсию

class GFG

{

  
/ * Узел списка ссылок * /

static class Node 

    int data; 

    Node next; 

    Node(int data)

    {

        this.data = data;

    }

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

    глава списка и INT, нажмите

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

static Node push( Node head, int new_data) 

    / * выделить узел * /

    Node new_node = new Node(new_data);

  

    / * вставить данные * /

    new_node.data = new_data; 

      

    new_node.next = head;

      

    head=new_node;

      

    return head;

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

    в качестве аргументов и возврата данных по индексу * /

static int GetNth( Node head, int n) 

    int count = 1

      

    // если количество равно тоже n, возвращаем node.data

    if(count == n) 

    return head.data; 

      

    // рекурсивно уменьшаем n и увеличиваем

    // голова к следующему указателю

    return GetNth(head.next, n - 1); 

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

public static void main(String args[])

    / * Начнем с пустого списка * /

    Node head = null

      

    / * Используйте push () для подтверждения ниже списка

    1.12.1.4.1 * /

    head=push(head,1); 

    head=push(head,4); 

    head=push(head,1); 

    head=push(head,12); 

    head=push(head,1); 

      

    / * Проверьте функцию подсчета * /

    System.out.printf("Element at index 3 is %d"

                                GetNth(head, 3)); 

}

// Этот код предоставлен Арнабом Кунду

python3

# Python3 программа для поиска n-го узла в
# связанный список с использованием рекурсии

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

    def __init__(self):

        self.head = None

  

    '' 'Учитывая ссылку (указатель на указатель) на

        Глава списка и INT, нажмите новый узел на

        передняя часть списка. «»»

    def push(self, new_data): # сделать новый узел и добавить

                              # в LinkedList

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

      

    def getNth(self, llist, position):

  

        # вызов рекурсивного метода

        llist.getNthNode(self.head, position, llist) 

  

    # рекурсивный метод для поиска N-го узла

    def getNthNode(self, head, position, llist): 

        count = 1 # инициализировать счет

        if(head):

            if count == position: # если число равно позиции,

                                  # это означает, что мы нашли позицию

                print(head.data)

            else

                llist.getNthNode(head.next, position - 1, llist) 

        else: # если голова не существует, у нас есть

              # перебрал LinkedList

            print('Index Doesn\'t exist')

  
Код водителя

if __name__=="__main__":

    llist = LinkedList() 

    llist.push(1

    llist.push(4

    llist.push(1

    llist.push(12

    llist.push(1

    # llist.getNth (llist, int (input ()))

    # Введите позицию узла здесь

    # первый аргумент - это экземпляр LinkedList

      

    print("Element at Index 3 is", end = " ")

    llist.getNth(llist, 3)

      
# Этот код предоставлен Йогешем Джоши

C #

// C # программа для поиска n-го узла в
// связанный список с использованием рекурсии

using System;

  

class GFG

{

  
/ * Узел списка ссылок * /

public class Node 

    public int data; 

    public Node next; 

    public Node(int data)

    {

        this.data = data;

    }

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

    глава списка и INT, нажмите

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

static Node push( Node head, int new_data) 

    / * выделить узел * /

    Node new_node = new Node(new_data);

  

    / * вставить данные * /

    new_node.data = new_data; 

      

    new_node.next = head;

      

    head = new_node;

      

    return head;

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

    в качестве аргументов и возврата данных по индексу * /

static int GetNth( Node head, int n) 

    int count = 1; 

      

    // если количество равно тоже n, возвращаем node.data

    if(count == n) 

    return head.data; 

      

    // рекурсивно уменьшаем n и увеличиваем

    // голова к следующему указателю

    return GetNth(head.next, n - 1); 

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

public static void Main()

    / * Начнем с пустого списка * /

    Node head = null

      

    / * Используйте push () для подтверждения ниже списка

    1.12.1.4.1 * /

    head=push(head,1); 

    head=push(head,4); 

    head=push(head,1); 

    head=push(head,12); 

    head=push(head,1); 

      

    / * Проверьте функцию подсчета * /

    Console.Write("Element at index 3 is {0}"

                                GetNth(head, 3)); 

}
}

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


Выход:

Element at index 3 is 1

Сложность времени: O (n)

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

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

Напишите функцию для получения N-го узла в связанном списке

0.00 (0%) 0 votes