От переводчика:

Данная статья является переводом статьи, опубликованной в блоге 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. Мы написали программу, решающую задачу в один проход с использованием подхода с двумя указателями, также известного как алгоритм зайца и черепахи, т.к. один указатель медленней второго. Это один из полезных приемов, т.к. вы можете использовать такой же алгоритм для определения цикла в связном списке, как показано тут. Вы также можете творчески подойти к использованию этого алгоритма при решении других проблем, когда необходим обход по связанному списку и манипулирование узлами одновременно.