Нахождение 3-го элемента от конца связного списка в Java

Данная статья является переводом статьи, опубликованной в блоге javarevisited. Она может быть интересна как новичкам, так и опытным программистам при подготовке к собеседованиям. В дальнейшем, планируется перевод цикла статей об алгоритмах и рецептах решений проблем как типового, так и академического характера. С удовольствием принимаются конструктивные предложения и замечания как по качеству перевода, так и по выбору новых статей

Нахождение 3-го элемента от конца в односвязном списке или n-го узла от хвоста является одним из каверзных и часто задаваемых вопросов по проблемам односвязных списков на собеседованиях. Задача, в данном случае, в том, чтобы решить проблему всего в один проход цикла, т.е., нельзя снова пройтись по связному списку и нельзя идти в обратном направлении, т.к. список односвязный. Если вы когда-нибудь решали проблемы связных списков, например, нахождение длины, вставки или удаления элементов, вы должны уже быть знакомы с вопросом обхода списков. В данной статье мы используем тот же самый алгоритм, который мы использовали для нахождения срединного элемента связного списка в один проход цикла. Этот алгоритм также известен как «алгоритм черепахи и зайца» из-за скорости двух указателей, используемых алгоритмом для обхода односвязного списка. Если вы помните, алгоритм использует два указателя — быстрый и медленный. Медленный указатель начинает обход, когда быстрый достигает N-ого элемента, например, для нахождения 3-го элемента от конца, второй указатель начнет обход, когда первый указатель достигнет 3-го элемента.

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

Это одна из многих проблем структур данных и и алгоритмических проблем, с которыми вы столкнетесь на типичном собеседовании (см. Cracking the Coding Interviews). Поскольку связанный список является популярной структурой данных, вопросы по нахождению в цикле и определению длины связанных списков, так же как и освещаемый в данной статье, довольно популярны.

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

Далее приведен полный листинг программы на Java по нахождению N-го элемента от конца односвязного списка. Данная программа решает задачу в один проход, т.е., обход связного списка производится только один раз. Как вы видите, мы использовали всего один цикл while в методе getLastNode(int n). Данный метод принимает целочисленный параметр и может использоваться для нахождения n-го элемента от конца связного списка, например, для 2-го элемента от хвоста, необходимо 2 шага, а для получения 3-го элемента списка — 3.

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

Далее приведено визуальное объяснение нахождения 2-го элемента от хвоста односвязного списка. Видно, как быстрый и медленный указатели проходят по списку, и когда быстрый указатель указывает на хвост, медленный указывает на n-й узел от конца.

Как программист, вы должны знать основные структуры данных и алгоритмы, например, что такое связный список, ее достоинства и недостатки и когда его использовать, например, он хорош для частого добавления и удаления элементов, но уже не так хорош для поиска, т.к. поиск элемента в связном списке занимает O(n) времени. Вы можете прочесть больше о связных списках в хороших книгах о структурах данных и алгоритмах, как, например, Введение в алгоритмы Томаса Х. Кормена — одной из лучших книг для изучения этой темы.

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

N-й узел от конца в односвязном списке

Вывод связный список: 1-->2-->3-->4 первый узел от конца: 4 второй узел от конца: 3 третий узел от хвоста:

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