От переводчика:
Данная статья является переводом статьи, опубликованной в блоге 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-й узел от конца в односвязном списке
public class Practice {
public static void main(String args[]) {
SinglyLinkedList list = new SinglyLinkedList();
list.append("1");
list.append("2");
list.append("3");
list.append("4");
System.out.println("связный список : " + list);
System.out.println("Первый узел от конца: " + list.getLastNode(1));
System.out.println("Второй узел от конца: " + list.getLastNode(2));
System.out.println("Третий узел от конца: " + list.getLastNode(3));
}
}
/**
* Реализация структуры данных в виде связного списка на Java
*
* @author Javin
*
*/
class SinglyLinkedList {
static class Node {
private Node next;
private String data;
public Node(String data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
private Node head; // Голова - это первый узел связного списка
/**
* проверяет, пуст ли список
*
* @возвращает true если связный список пуст, т.е., узлов нет
*/
public boolean isEmpty() {
return length() == 0;
}
/**
* добавляет узел в хвост связного списка
*
* @param data
*/
public void append(String data) {
if (head == null) {
head = new Node(data);
return;
}
tail().next = new Node(data);
}
/**
* возвращает последний узел или хвост данного связного списка
*
* @return последний узел
*/
private Node tail() {
Node tail = head;
// Находит последний элемент связного списка, известный как хвост
while (tail.next != null) {
tail = tail.next;
}
return tail;
}
/**
* метод возвращающий длину связного списка
*
* @return длину, т.е, число узлов в связном списке
*/
public int length() {
int length = 0;
Node current = head;
while (current != null) {
length++;
current = current.next;
}
return length;
}
/**
* получения n-го узла от конца
*
* @param n
* @return n-й узел от последнего
*/
public String getLastNode(int n) {
Node fast = head;
Node slow = head;
int start = 1;
while (fast.next != null) {
fast = fast.next;
start++;
if (start > n) {
slow = slow.next;
}
}
return slow.data;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node current = head;
while (current != null) {
sb.append(current).append("-->");
current = current.next;
}
if (sb.length() >= 3) {
sb.delete(sb.length() - 3, sb.length());
}
return sb.toString();
}
}
Вывод
связный список: 1-->2-->3-->4
первый узел от конца: 4
второй узел от конца: 3
третий узел от хвоста:
Вот и все о нахождении 3-го элемента с конца связного списка в Java. Мы написали программу, решающую задачу в один проход с использованием подхода с двумя указателями, также известного как алгоритм зайца и черепахи, т.к. один указатель медленней второго. Это один из полезных приемов, т.к. вы можете использовать такой же алгоритм для определения цикла в связном списке, как показано тут. Вы также можете творчески подойти к использованию этого алгоритма при решении других проблем, когда необходим обход по связанному списку и манипулирование узлами одновременно.
Автор: caesar_84
