Поиск среднего элемента в связанном списке

Ссылка на сайт:-

Описание :-

Дан односвязный список из N узлов. Задача состоит в том, чтобы найти середину связанного списка.

Например, если задан связанный список 10->20->30->40->50, то на выходе должно быть 30.

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

Пример 1:

Input:
LinkedList: 1->2->3->4->5
Output: 3

Пример 2:

Input:
LinkedList: 2->4->6->7->5->1
Output: 7

Ожидаемая временная сложность:O(N).
Ожидаемое вспомогательное пространство:O(1).

Ограничения:
1 ‹= N ‹= 5000

Способ 1 – 

Шаг 1: Пройдите по связанному списку от начала до конечного узла. Подсчитайте количество узлов при обходе связанного списка.

Шаг 2. Подсчет количества узлов в связанном списке, разделенный на 2, даст среднее значение.

Шаг 3: Снова пройдите по связанному списку от головного узла до среднего значения. Наконец, верните данные в средний узел.

Ниже приведено решение java для этой проблемы:

class Solution {
    public ListNode middleNode(ListNode head) {
        
       // get the length of the linked list
    int len = 0;
    ListNode current = head;
    while (current != null) {
        len++;
        current = current.next;
    }
    current = head;
    int mid = len / 2;
    for (int i = 0; i < mid; i++) {
        current = current.next;
    }
    return current;
    }
}

Способ 2: -

Шаг 1: создайте два указателя — быстрый и медленный. Оба этих указателя будут указывать на начало заголовка в начале.

Шаг 2 : Затем увеличьте быстрый указатель на 2 узла и медленный указатель на один узел.

Шаг 3: Когда быстрый указатель достигнет конца списка, медленный указатель дойдет до середины списка, и мы получим наш результат.

Ниже приведено решение java для этой проблемы:

class Solution {
    public ListNode middleNode(ListNode head) {
        
        if(head == null){
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
        
    }
}