Рубрики

Найти середину данного связанного списка в C и Java

Имея односвязный список, найдите середину связанного списка. Например, если данный список связан с 1-> 2-> 3-> 4-> 5, то результат должен быть равен 3.

Если есть даже узлы, то будет два средних узла, нам нужно напечатать второй средний элемент. Например, если данный список связан с 1-> 2-> 3-> 4-> 5-> 6, то результат должен быть 4.

Способ 1:
Пройдите по всему связанному списку и посчитайте номер. узлов. Теперь просмотрите список снова до count / 2 и верните узел в count / 2.

Способ 2:
Пройдите по связанному списку, используя два указателя. Переместить один указатель на один, а другой указатель на два. Когда быстрый указатель достигает конца, медленный указатель достигает середины связанного списка.

На рисунке ниже показано, как работает функция printMiddle в коде:

С

#include<stdio.h> 
#include<stdlib.h> 

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

struct Node 

    int data; 

    struct Node* next; 

}; 

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

void printMiddle(struct Node *head) 

    struct Node *slow_ptr = head; 

    struct Node *fast_ptr = head; 

  

    if (head!=NULL) 

    

        while (fast_ptr != NULL && fast_ptr->next != NULL) 

        

            fast_ptr = fast_ptr->next->next; 

            slow_ptr = slow_ptr->next; 

        

        printf("The middle element is [%d]\n\n", slow_ptr->data); 

    

  

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 *ptr) 

    while (ptr != NULL) 

    

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

        ptr = ptr->next; 

    

    printf("NULL\n"); 

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

int main() 

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

    struct Node* head = NULL; 

    int i; 

  

    for (i=5; i>0; i--) 

    

        push(&head, i); 

        printList(head); 

        printMiddle(head); 

    

  

    return 0; 

CPP

#include<bits/stdc++.h> 

using namespace std; 

  
// Структура

struct Node 

    int data; 

    struct Node* next; 

}; 

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

void printMiddle(struct Node *head) 

    struct Node *slow_ptr = head; 

    struct Node *fast_ptr = head; 

  

    if (head!=NULL) 

    

        while (fast_ptr != NULL && fast_ptr->next != NULL) 

        

            fast_ptr = fast_ptr->next->next; 

            slow_ptr = slow_ptr->next; 

        

        printf("The middle element is [%d]\n\n", slow_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; 

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

void printList(struct Node *ptr) 

    while (ptr != NULL) 

    

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

        ptr = ptr->next; 

    

    printf("NULL\n"); 

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

int main() 

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

    struct Node* head = NULL; 

      

    // Итерация и добавление элемента

    for (int i=5; i>0; i--) 

    

        push(&head, i); 

        printList(head); 

        printMiddle(head); 

    

  

    return 0; 

Джава

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

class LinkedList

{

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

  

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

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

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

    void printMiddle()

    {

        Node slow_ptr = head;

        Node fast_ptr = head;

        if (head != null)

        {

            while (fast_ptr != null && fast_ptr.next != null)

            {

                fast_ptr = fast_ptr.next.next;

                slow_ptr = slow_ptr.next;

            }

            System.out.println("The middle element is [" +

                                slow_ptr.data + "] \n");

        }

    }

  

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

    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 void printList()

    {

        Node tnode = head;

        while (tnode != null)

        {

            System.out.print(tnode.data+"->");

            tnode = tnode.next;

        }

        System.out.println("NULL");

    }

  

    public static void main(String [] args)

    {

        LinkedList llist = new LinkedList();

        for (int i=5; i>0; --i)

        {

            llist.push(i);

            llist.printList();

            llist.printMiddle();

        }

    }

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


Выход:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Способ 3:
Инициализируйте средний элемент как заголовок и инициализируйте счетчик как 0. Пройдите по списку от заголовка, перемещаясь, увеличивайте счетчик и меняйте середину на середину-> следующий, когда счетчик нечетный. Таким образом, середина будет перемещать только половину общей длины списка.
Спасибо Нарендре Кангралкару за предложенный метод.

#include<stdio.h>
#include<stdlib.h>

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

struct node

{

    int data;

    struct node* next;

};

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

void printMiddle(struct node *head)

{

    int count = 0;

    struct node *mid = head;

  

    while (head != NULL)

    {

        / * обновить середину, когда 'count' - нечетное число * /

        if (count & 1)

            mid = mid->next;

  

        ++count;

        head = head->next;

    }

  

    / * если указан пустой список * /

    if (mid != NULL)

        printf("The middle element is [%d]\n\n", mid->data);

}

  

  

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 *ptr)

{

    while (ptr != NULL)

    {

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

        ptr = ptr->next;

    }

    printf("NULL\n");

}

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

int main()

{

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

    struct node* head = NULL;

    int i;

  

    for (i=5; i>0; i--)

    {

        push(&head, i);

        printList(head);

        printMiddle(head);

    }

  

    return 0;

}

Выход:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

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

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

Найти середину данного связанного списка в C и Java

0.00 (0%) 0 votes