Статьи

Как найти средний элемент связанного списка в Java за один проход

Ноябрь 5, 2018

Как вы находите средний элемент LinkedList за один проход — это вопрос программирования, который часто задают программистам Java и не Java в телефонном интервью. Этот вопрос похож на проверку палиндрома или
вычисление факториала , где интервьюер иногда также просит написать код. Чтобы ответить на этот вопрос, кандидат должен быть знаком со структурой данных LinkedList, т. Е. В случае одиночного LinkedList каждый узел Linked List содержит данные и указатель, который является адресом следующего Linked List, а последний элемент Singlely Linked List указывает на ноль. Так как для того, чтобы найти средний элемент связанного списка, вам нужно найти длину связанного списка, которая считает элементы до конца, т.е. до тех пор, пока вы не найдете последний элемент связанного списка.

Что делает эту структуру данных интересной для интервью: вам нужно найти средний элемент inkedList
за один проход, и вы не знаете длину LinkedList.

Именно здесь проверяется логическая способность кандидата, независимо от того, знаком он с пространственно-временным компромиссом или нет.

Как будто вы тщательно обдумываете, вы можете решить эту проблему, используя два указателя, как упомянуто в моем последнем посте « Как найти длину односвязного списка в Java» .

Используя два указателя, увеличивая один на каждой итерации и другой на каждой второй итерации. Когда первый указатель будет указывать на конец связанного списка, второй указатель будет указывать на средний узел связанного списка.

На самом деле, этот подход с двумя указателями может решить несколько подобных проблем, таких как
как найти третий узел из последнего в связанном списке за одну итерацию или как найти N-й элемент из последнего в связанном списке. В этом руководстве по программированию на Java мы увидим программу на Java, которая находит средний элемент связанного списка за одну итерацию.

Как найти средний элемент LinkedList за один проход

Вот полная Java-программа для поиска среднего узла Linked List в Java. Помните, что класс LinkedList здесь — это наш пользовательский класс, и не путайте этот класс с java.util.LinkedList, который является популярным классом Collection в Java.

В этой Java-программе наш класс LinkedList представляет структуру данных связанного списка, которая содержит коллекцию узла и имеет голову и хвост.

Каждый узел содержит данные и адресную часть. Основным методом
Класс LinkedListTest используется для имитации проблемы, где мы создали Linked List и добавили в него несколько элементов, а затем перебрали их, чтобы найти средний элемент связанного списка за один проход в Java.

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

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
import test.LinkedList.Node;
 
/**
 * Java program to find middle element of linked list in one pass.
 * In order to find middle element of a linked list
 * we need to find the length first but since we can only
 * traverse linked list one time, we will have to use two pointers
 * one which we will increment on each iteration while
 * other which will be incremented every second iteration.
 * So when the first pointer will point to the end of a
 * linked list, second will be pointing to the middle
 * element of a linked list
 *
 * @author Javin Paul
 */
public class LinkedListTest {
   
   
    public static void main(String args[]) {
        //creating LinkedList with 5 elements including head
      LinkedList linkedList = new LinkedList();
      LinkedList.Node head = linkedList.head();
      linkedList.add( new LinkedList.Node("1"));
      linkedList.add( new LinkedList.Node("2"));
      linkedList.add( new LinkedList.Node("3"));
      linkedList.add( new LinkedList.Node("4"));
     
      //finding middle element of LinkedList in single pass
      LinkedList.Node current = head;
      int length = 0;
      LinkedList.Node middle = head;
     
      while(current.next() != null){
          length++;
          if(length%2 ==0){
              middle = middle.next();
          }
          current = current.next();
      }
     
      if(length%2 == 1){
          middle = middle.next();
      }
 
      System.out.println("length of LinkedList: " + length);
      System.out.println("middle element of LinkedList : "                                  + middle);
       
    }
   
}
 
class LinkedList{
    private Node head;
    private Node tail;
   
    public LinkedList(){
        this.head = new Node("head");
        tail = head;
    }
   
    public Node head(){
        return head;
    }
   
    public void add(Node node){
        tail.next = node;
        tail = node;
    }
   
    public static class Node{
        private Node next;
        private String data;
 
        public Node(String data){
            this.data = data;
        }
       
        public String data() {
            return data;
        }
 
        public void setData(String data) {
            this.data = data;
        }
 
        public Node next() {
            return next;
        }
 
        public void setNext(Node next) {
            this.next = next;
        }
       
        public String toString(){
            return this.data;
        }
    }
}
 
Output:
length of LinkedList: 4
middle element of LinkedList: 2

Это все о том, как найти средний элемент LinkedList за один проход. Как я уже сказал, это хороший вопрос для интервью, чтобы отделить программистов от непрограммистов. Кроме того, методика, упомянутая здесь, чтобы найти средний узел LinkedList, может быть использована для поиска третьего элемента из Last или
n-й элемент из последнего в LinkedList.

Если вам понравилась эта статья и вы хотели бы попробовать несколько более сложных упражнений по программированию, взгляните на следующие вопросы по программированию из различных интервью:

  • Как проверить, содержит ли LinkedList какой-либо цикл в Java? ( решение )
  • Как искать элемент в массиве в Java? ( решение )
  • Как отсортировать массив с помощью алгоритма пузырьковой сортировки? ( алгоритм )
  • Как рассчитать сумму цифр числа в Java? ( Решение )
  • Написать программу для поиска первых неповторяющихся символов из строки в Java? ( программа )
  • Как проверить, является ли число двоичным в Java? ( ответ )
  • Напишите программу, чтобы проверить, является ли число Prime или нет? ( решение )
  • Как предотвратить тупик в Java? ( решение )
  • Как найти наибольший простой фактор числа в Java? ( решение )
  • Как рассчитать факториал, используя рекурсию в Java? ( алгоритм )
  • Как объявить и инициализировать двумерный массив в Java? ( решение )
  • Написать метод для подсчета вхождений символа в строке? ( Решение )
  • Как проверить, является ли номер Армстронг номером или нет? ( решение )
  • Написать Программу удаления дубликатов из массива без использования Collection API? ( программа )
  • Как обратить String в Java без использования методов API? ( Решение )
  • Написать метод для удаления дубликатов из ArrayList в Java? ( Решение )
  • Напишите программу, чтобы проверить, является ли число палиндромом или нет? ( программа )
  • Напишите программу, чтобы проверить, содержит ли массив повторяющийся номер или нет? ( Решение )
  • Как найти последовательность Фибоначчи до заданного числа? ( решение )
  • Написать программу для поиска пропущенного числа в отсортированном массиве? ( алгоритм )
  • 10 баллов о массиве в Java? ( должен знать факты )
  • Как найти два верхних максимума на целочисленном массиве в Java? ( решение )
  • Напишите метод проверки, если две строки являются анаграммами друг друга? ( метод )
  • Как найти самое большое и наименьшее число в массиве? ( решение )
  • Написать функцию, чтобы найти средний элемент связанного списка за один проход? ( решение )
  • Как решить проблему «производитель-потребитель» в Java. ( решение )
  • Напишите программу для проверки, является ли число степенью двойки или нет? ( программа )

Спасибо за чтение этого вопроса интервью кодирования до сих пор. Если вам нравится этот вопрос об интервью с String, поделитесь им с друзьями и коллегами. Если у вас есть какие-либо вопросы или пожелания, оставьте комментарий.

См. Оригинальную статью здесь: Как найти средний элемент связанного списка в Java за один проход

Мнения, высказанные участниками Java Code Geeks, являются их собственными.

63
Share: