Рубрики

Программа для n-го узла из конца связанного списка

При наличии связанного списка и числа n напишите функцию, которая возвращает значение в n-м узле в конце связанного списка.

Например, если входное значение находится ниже списка и n = 3, то выходное значение равно «B».

Способ 1 (Использовать длину связанного списка)
1) Рассчитайте длину связанного списка. Пусть длина будет длина.
2) Распечатать (len — n + 1) -й узел от начала связанного списка.

C / C ++

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

using namespace std;

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

struct Node {

    int data;

    struct Node* next;

};

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

void printNthFromLast(struct Node* head, int n)

{

    int len = 0, i;

    struct Node* temp = head;

  

    // подсчитываем количество узлов в связанном списке

    while (temp != NULL) {

        temp = temp->next;

        len++;

    }

  

    // проверяем, не равно ли значение n

    // больше длины связанного списка

    if (len < n)

        return;

  

    temp = head;

  

    // получаем (len-n + 1) -й узел с начала

    for (i = 1; i < len - n + 1; i++)

        temp = temp->next;

  

    cout << temp->data;

  

    return;

}

  

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

{

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

    struct Node* new_node = new Node();

  

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

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref) = new_node;

}

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

int main()

{

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

    struct Node* head = NULL;

  

    // создаем ссылку 35-> 15-> 4-> 20

    push(&head, 20);

    push(&head, 4);

    push(&head, 15);

    push(&head, 35);

  

    printNthFromLast(head, 4);

    return 0;

}

Джава

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

class LinkedList {

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

  

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

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

       связанный список * /

    void printNthFromLast(int n)

    {

        int len = 0;

        Node temp = head;

  

        // 1) подсчитать количество узлов в связанном списке

        while (temp != null) {

            temp = temp.next;

            len++;

        }

  

        // проверяем, не превышает ли значение n длину

        // связанный список

        if (len < n)

            return;

  

        temp = head;

  

        // 2) получить (len-n + 1) -й узел с начала

        for (int i = 1; i < len - n + 1; i++)

            temp = temp.next;

  

        System.out.println(temp.data);

    }

  

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

    public void push(int new_data)

    {

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

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

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.push(20);

        llist.push(4);

        llist.push(15);

        llist.push(35);

  

        llist.printNthFromLast(4);

    }

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

python3

# Простая программа на Python3 для поиска
# н-ный конец

class Node:

    def __init__(self, new_data):

        self.data = new_data

        self.next = None

      

class LinkedList:

    def __init__(self):

        self.head = None

  

    # createNode и и сделать связанный список

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    # Функция для получения n-го узла из

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

    def printNthFromLast(self, n):

        temp = self.head # используемая временная переменная

          

        length = 0

        while temp is not None:

            temp = temp.next

            length += 1

          

        # количество печати

        if n > length: # если введенное местоположение больше

                       # чем длина связанного списка

            print('Location is greater than the' +

                         ' length of LinkedList')

            return

        temp = self.head

        for i in range(0, length - n):

            temp = temp.next

        print(temp.data)

  
Код водителя

llist = LinkedList() 

llist.push(20

llist.push(4

llist.push(15

llist.push(35)

llist.printNthFromLast(4)

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

C #

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

using System;

  

public class LinkedList

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

  

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

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        

            data = d; 

            next = null

        

    

  

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

    связанный список * /

    void printNthFromLast(int n) 

    

        int len = 0; 

        Node temp = head; 

  

        // 1) подсчитать количество узлов в связанном списке

        while (temp != null

        

            temp = temp.next; 

            len++; 

        

  

        // проверяем, не превышает ли значение n длину

        // связанный список

        if (len < n) 

            return

  

        temp = head; 

  

        // 2) получить (len-n + 1) -й узел с начала

        for (int i = 1; i < len - n + 1; i++) 

            temp = temp.next; 

  

        Console.WriteLine(temp.data); 

    

  

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

    public void push(int new_data) 

    

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

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

        Node new_node = new Node(new_data); 

  

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

        new_node.next = head; 

  

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

        head = new_node; 

    

  

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

    public static void Main(String[] args) 

    

        LinkedList llist = new LinkedList(); 

        llist.push(20); 

        llist.push(4); 

        llist.push(15); 

        llist.push(35); 

  

        llist.printNthFromLast(4); 

    

}

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

Выход:

 35 

Ниже приведен рекурсивный код C для того же метода. Спасибо Anuj Bansal за предоставление следующего кода.

void printNthFromLast(struct Node* head, int n)

{

    static int i = 0;

    if (head == NULL)

        return;

    printNthFromLast(head->next, n);

    if (++i == n)

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

}

Сложность времени: O (n), где n — длина связанного списка.
Метод 2 (Используйте два указателя)
Поддерживайте два указателя — указатель ссылки и основной указатель. Инициализируйте и ссылку, и главные указатели на голову. Сначала переместите ссылочный указатель на n узлов из головы. Теперь перемещайте оба указателя по одному, пока указатель ссылки не достигнет конца. Теперь основной указатель будет указывать на n-й узел с конца. Вернуть основной указатель.

Ниже приведен пробный запуск вышеуказанного подхода:

Ниже приведена реализация вышеуказанного подхода:

C / C ++

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

using namespace std;

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

struct Node

{

  int data;

  struct Node* next;

};

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

void printNthFromLast(struct Node *head, int n)

{

  struct Node *main_ptr = head;

  struct Node *ref_ptr = head;

  

  int count = 0;

  if(head != NULL)

  {

     while( count < n )

     {

        if(ref_ptr == NULL)

        {

           printf("%d is greater than the no. of "

                    "nodes in list", n);

           return;

        }

        ref_ptr = ref_ptr->next;

        count++;

     } / * Конец времени * /

  

     while(ref_ptr != NULL)

     {

        main_ptr = main_ptr->next;

        ref_ptr  = ref_ptr->next;

     }

     printf("Node no. %d from last is %d "

              n, main_ptr->data);

  }

}

  

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

{

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

  struct Node* new_node = new Node(); 

  

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

  new_node->data  = new_data;

  

  / * связать старый список с новым узлом * /

  new_node->next = (*head_ref);    

  

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

  (*head_ref)    = new_node;

}

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

int main()

{

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

  struct Node* head = NULL;

  push(&head, 20);

  push(&head, 4);

  push(&head, 15);

  push(&head, 35);

  

  printNthFromLast(head, 4);

}

Джава

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

class LinkedList {

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

  

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

    class Node {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    void printNthFromLast(int n)

    {

        Node main_ptr = head;

        Node ref_ptr = head;

  

        int count = 0;

        if (head != null) {

            while (count < n) {

                if (ref_ptr == null) {

                    System.out.println(n + " is greater than the no "

                                       + " of nodes in the list");

                    return;

                }

                ref_ptr = ref_ptr.next;

                count++;

            }

            while (ref_ptr != null) {

                main_ptr = main_ptr.next;

                ref_ptr = ref_ptr.next;

            }

            System.out.println("Node no. " + n + " from last is " + main_ptr.data);

        }

    }

  

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

    public void push(int new_data)

    {

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

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

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    public static void main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.push(20);

        llist.push(4);

        llist.push(15);

        llist.push(35);

  

        llist.printNthFromLast(4);

    }

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

питон

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

  
# Класс узла

class Node:

  

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

    def __init__(self, data):

        self.data = data

        self.next = None

  

class LinkedList:

  

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

    def __init__(self):

        self.head = None

  

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

    def push(self, new_data):

        new_node = Node(new_data)

        new_node.next = self.head

        self.head = new_node

  

    def printNthFromLast(self, n):

        main_ptr = self.head

        ref_ptr = self.head 

      

        count = 0 

        if(self.head is not None):

            while(count < n ):

                if(ref_ptr is None):

                    print "% d is greater than the no. pf nodes in list" %(n)

                    return

   

                ref_ptr = ref_ptr.next

                count += 1

  

        while(ref_ptr is not None):

            main_ptr = main_ptr.next 

            ref_ptr = ref_ptr.next

  

        print "Node no. % d from last is % d " %(n, main_ptr.data)

  

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

llist = LinkedList()

llist.push(20)

llist.push(4)

llist.push(15)

llist.push(35)

  

llist.printNthFromLast(4)

  
# Этот код предоставлен Nikhil Kumar Singh (nickzuck_007)

C #

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

using System;

  

public class LinkedList

{

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

  

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

    public class Node 

    {

        public int data;

        public Node next;

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    void printNthFromLast(int n)

    {

        Node main_ptr = head;

        Node ref_ptr = head;

  

        int count = 0;

        if (head != null)

        {

            while (count < n) 

            {

                if (ref_ptr == null)

                {

                    Console.WriteLine(n + " is greater than the no "

                                    + " of nodes in the list");

                    return;

                }

                ref_ptr = ref_ptr.next;

                count++;

            }

            while (ref_ptr != null)

            {

                main_ptr = main_ptr.next;

                ref_ptr = ref_ptr.next;

            }

            Console.WriteLine("Node no. " + n + " from last is " + main_ptr.data);

        }

    }

  

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

    public void push(int new_data)

    {

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

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

        Node new_node = new Node(new_data);

  

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

        new_node.next = head;

  

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

        head = new_node;

    }

  

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

    public static void Main(String[] args)

    {

        LinkedList llist = new LinkedList();

        llist.push(20);

        llist.push(4);

        llist.push(15);

        llist.push(35);

  

        llist.printNthFromLast(4);

    }

}

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


Выход:

Node no. 4 from last is 35

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

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенные выше коды / алгоритмы неверны, или найдете другие способы решения той же проблемы.

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

Программа для n-го узла из конца связанного списка

0.00 (0%) 0 votes