Как найти n-й элемент в конце односвязного списка?

Ваш алгоритм работает, сначала создавая ссылки на два узла в вашем связанном списке, которые находятся на N узлах друг от друга. Таким образом, в вашем примере, если N равно 7, тогда он установит p1 на 8 и p2 на 4.

Затем он будет перемещать каждую ссылку на узел к следующему узлу в списке, пока p2 не достигнет последнего элемента в списке. Опять же, в вашем примере это будет, когда p1 равно 5, а p2 равно 10. В этот момент p1 относится к N-му последнему элементу в списке (по свойству, что они находятся на N узлах друг от друга).

Ключом к этому алгоритму является установка двух указателей p1 и p2 на расстоянии n-1 узлов, поэтому мы хотим, чтобы p2 указывал на узел (n-1)th с начала списка, а затем перемещаем p2, пока он не достигнет узла last списка. Как только p2 достигнет конца списка, p1 будет указывать на n-й узел с конца списка.

Я поместил объяснение в виде комментариев. Надеюсь, поможет:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

В качестве альтернативы мы можем установить p1 и p2 на n узлов вместо (n-1), а затем переместить p2 до конца списка вместо перемещения до последнего узла:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Что вы думаете об этом подходе?

1. Подсчитайте длину связанного списка.
2. Фактический индекс узла из головы = длина связанного списка - данный индекс;
3. Напишите функцию для перехода от головы и получите узел с указанным выше индексом.

Здесь уже есть много ответов, но все они проходят по списку дважды (последовательно или параллельно) или используют много дополнительного хранилища.

Вы можете сделать это, просматривая список только один раз (плюс немного), используя постоянное дополнительное пространство:

Node *getNthFromEnd(Node *list, int n) {

    if (list == null || n<1) {
        return null; //no such element
    }

    Node *mark1 = list, *mark2 = list, *markend = list;
    int pos1 = 0, pos2 = 0, posend = 0;

    while (markend!=null) {
        if ((posend-pos2)>=(n-1)) {
            mark1=mark2;
            pos1=pos2;
            mark2=markend;
            pos2=posend;
        }
        markend=markend->next;
        ++posend;
    }
    if (posend<n) {
        return null; //not enough elements in the list
    }

    //mark1 and mark2 are n-1 elements apart, and the end is at least
    //1 element after mark2, so mark1 is at least n elements from the end

    while((posend - pos1) > n) {
      mark1 = mark1->next;
      ++pos1;
    }
    return mark1;
}

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

Если вы используете M дополнительных указателей, вы можете уменьшить их до N+ceil(n/(M-1)) (и вы должны хранить их в кольцевом буфере)

Вы можете просто просмотреть связанный список и получить размер. Когда у вас есть размер, вы можете найти n-й член в 2n, который все еще равен O (n).

public T nthToLast(int n) {
    // return null if linkedlist is empty
    if (head == null) return null;

    // declare placeholder where size of linkedlist will be stored
    // we are hoping that size of linkedlist is less than MAX of INT
    int size = 0;

    // This is O(n) for sure
    Node i = head;
    while (i.next != null) {
        size += 1;
        i = i.next;
    }

    // if user chose something outside the size of the linkedlist return null
    if (size < n)
        return null;

    // This is O(n) if n == size
    i = head;
    while(size > n) {
        size--;
        i = i.next;
    }

    // Time complexity = n + n = 2n
    // therefore O(n)

    return i.value;
}

Поскольку это звучит как домашнее задание, я предпочитаю помогать вам самим, а не предлагать реальное решение.

Я предлагаю вам запустить этот код на небольшом наборе данных. Используйте отладчик для пошагового выполнения строк (вы можете установить точку останова в начале функции). Это должно дать вам представление о том, как работает код.

Вы также можете Console.WriteLine() выводить интересующие вас переменные.

Нет, вы не знаете длину связанного списка ... Вам придется пройти один раз, чтобы получить длину списка понравившихся, поэтому ваш подход малоэффективен;

Еще одно решение этой проблемы. Хотя временная сложность остается прежней, этот код достигает решения за один цикл.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
    {
        Link current = linkedList.getFirst();//current node
        Link currentK = linkedList.getFirst();//node at index k

        int counter = 0;

        while(current.getNext()!=null)
        {
            counter++;

            if(counter>=k)
            {
                currentK = currentK.getNext();
            }

            current = current.getNext();
        }

        //reached end
        return currentK;
    }

Просто переверните связанный список за линейное время и найдите k-й элемент. Он по-прежнему работает в линейном времени.

У меня есть рекурсивное решение в другом потоке в StackOverflow здесь

Здесь мы берем два указателя pNode и qNode, оба начальные точки на головной qNode. Затем перейдите до конца списка, и pNode будет перемещаться только тогда, когда разница между счетчиком и позицией больше 0, а pthNode увеличивается один раз в каждом цикле.

static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
    count++;
    if(count - pos > 0)
        pNode=pNode.next;
    qNode=qNode.next;
}
return pNode;
}

Используйте два указателя pTemp и NthNode. Изначально оба указывают на головной узел списка. NthNode начинает движение только после того, как pTemp сделает n ходов. От обоих идет вперед, пока pTemp не достигнет конца списка. В результате NthNode указывает на n-й узел с конца связанного списка.

public ListNode NthNodeFromEnd(int n){
    ListNode pTemp = head, NthNode = null;
   for(int count=1; count<n;count++){
     if(pTemp!=null){
       pTemp = pTemp.getNext();
     }
   }
   while(pTemp!=null){
     if(NthNode==null){
         NthNode = head;
     }
     else{
        NthNode = NthNode.getNext();
     }
     pTemp = pTemp.getNext();
   }
   if(NthNode!=null){
     NthNode = NthNode.getNext();
     return NthNode;
   }
return null;
}

См. Учебник: «Упрощение структуры данных и алгоритмов в Java»

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

То, что мы делаем в этом примере, будет таким же, нам просто нужен фрейм с шириной n элементов, и что нам нужно сделать, это поместить фрейм в конец списка, таким образом, начальный узел фрейма будет ровно n- th элемент в конец списка.

Это наш список, предполагающий, что у нас есть M элементов в списке и наш фрейм шириной N элементов;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

<-- Frame -->

Однако нам нужны только границы кадра, поэтому конечная граница кадра будет ровно (N-1) элементов от начальной границы кадра. Так что нужно хранить только эти граничные элементы. Назовем их A и B;

HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M)

A <- N-Element Wide-> B

Первое, что нам нужно сделать, это найти точку B, которая является концом кадра.

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
    b = b.next;
    count++;
}

Теперь b является n-м элементом массива, а a находится в HEAD. Итак, наш фрейм установлен, мы будем шаг за шагом увеличивать оба граничных узла, пока b не дойдет до конца списка, где a будет от n-го до -последний элемент;

ListNode<T> a = head;

while(b.next != null) {
    a = a.next;
    b = b.next;
}

return a;

Чтобы собрать все, и с проверками HEAD, N ‹M (где M - размер списка) проверок и прочего, вот метод полного решения;

public ListNode<T> findNthToLast(int n) {
    if(head == null) {
        return null;
    } else {
        ListNode<T> b = head;
        int count = 1;

        while(count < n && b != null) {
            b = b.next;
            count++;
        }

        if(count == n && b!=null) {
            ListNode<T> a = head;

            while(b.next != null) {
                a = a.next;
                b = b.next;
            }

            return a;
        } else {
            System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
            return null;
        }
    }
}

Вы также можете решить указанную выше проблему с помощью хеш-таблиц. Записи хеш-таблицы - это позиция узла и адрес узла. Итак, если мы хотим найти n-й узел с конца (это означает m-n + 1 от первого, где m - количество узлов). Теперь, когда мы вводим записи хеш-таблицы, мы получаем количество узлов. Шаги: -

1.Пройдите по каждому узлу и сделайте соответствующие записи в хеш-таблице.

2. Ищем m-n + 1 узел в хеш-таблице, мы получаем адрес.

Сложность по времени - O (n).

Я думаю, что в коде вопроса есть один недостаток, и мне интересно, взят ли он из книги, как это возможно ... он может выполняться правильно, но код несколько логически неверен. Внутри цикла for ... условие if должно быть проверено на p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
       if (p2->next == null) {
       return null; // not found since list size < n
   }

... отдых в порядке, и объяснение, как уже было дано, код сдвигает p2 (n-1) позиции продвигаются к p1, затем в цикле while он перемещает их одновременно, пока p2->next не достигнет конца ... не стесняйтесь сказать, считаете ли вы мой ответ неправильным

Задача, приведенная в книге «Кубка карьеры», немного другая. В нем говорится, что найти с n-го по последний элемент односвязного списка.

Вот мой код:

    public void findntolast(int index)
    {
        Node ptr = front; int count = 0;
        while(ptr!=null)
        {
            count++;
            if (count == index)
            {
                front = ptr;
                break;
            }
            ptr = ptr.next;
        }
        Node temp=front;
        while(temp!=null)
        {
            Console.WriteLine(temp.data);
            temp=temp.next;
        }
    }

Рекурсивное решение:

Node findKth (Node head, int count, int k) {
    if(head == null)
        return head;
    else {
        Node n =findKth(head.next,count,k);
        count++;

        if(count == k)
            return head;

        return n;
    }
}

Можете ли вы использовать дополнительную структуру данных ... если да, то это будет просто ... начните помещать все узлы в стек, поддерживать счетчик и вытолкнуть его. согласно вашему примеру, 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10 начните читать связанный список и начните нажимать узлы или данные node-> на стек. поэтому стек будет выглядеть так: верх -> {10, 10,4, 5, 1, 2, 7, 5, 10, 8} ‹- низ.

теперь начните появляться с вершины стека, поддерживая счетчик = 1, и каждый раз, когда вы нажимаете, увеличивайте счетчик на 1, когда вы достигнете n-го элемента (в вашем примере 7-й элемент), прекратите всплывать.

примечание: это будет печатать или извлекать данные / узлы в обратном порядке

Вот код, использующий подход с двумя указателями: (источник)

Подход с медленным и быстрым указателем

struct node
{
  int data;
  struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
  mynode *ptr1,*ptr2;
  int count;

  if(!head)
  {
    return(NULL);
  }

  ptr1  = head;
  ptr2  = head;
  count = 0;

  while(count < n)
  {
     count++;
     if((ptr1=ptr1->next)==NULL)
     {
        //Length of the linked list less than n. Error.
        return(NULL);
     }
  }

  while((ptr1=ptr1->next)!=NULL)
  {
    ptr2=ptr2->next;
  }

  return(ptr2);
}

Рекурсия

node* findNthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return 0;
    }
    node* retval = findNthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

мой подход, который я считаю простым и имеет временную сложность O (n).

Шаг 1. Сначала подсчитайте количество узлов. Запустите цикл for, начиная с первого узла до последнего узла

Шаг 2: Когда у вас есть счетчик, примените простую математику, например, если мы нашли 7-й узел к последнему узлу, а количество всех узлов равно 12, то (count - index) - 1 даст некоторый k-й узел, до которого вам нужно будет пройти, и это будет n-й узел до последнего узла. В этом случае (12-7) -1 = 4

Если элементы 8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10, то результат с 7-го по последний узел равен 7, что является не чем иным, как 4-м узлом из начало.

В java я буду использовать -

public class LL {
  Node head;
  int linksCount;

   LL(){
     head = new Node();
     linksCount = 0;
   }

  //TRAVERSE TO INDEX
  public Node getNodeAt(int index){
    Node temp= head;
    if(index > linksCount){
        System.out.println("index out of bound !");
        return null;
    }
    for(int i=0;i<index && (temp.getNext() != null);i++){
        temp = temp.getNext();
    }
    return temp.getNext();
  }
}

Здесь никто не заметил, что версия Джонатана выдаст исключение NullPinterException, если n больше, чем длина LinkedList. Вот моя версия:

public Node nth(int n){
        if(head == null || n < 1) return null;

        Node n1 = head;
        Node n2 = head;
        for(int i = 1; i < n; i++){
            if(n1.next == null) return null; 
            n1 = n1.next;
        }

        while (n1.next != null){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n2;
}

Я просто вношу здесь небольшие изменения: когда узел n1 продвигается вперед, вместо проверки, является ли n1 нулевым, я проверяю, что погода n1.next имеет значение null, иначе в цикле while n1.next вызовет исключение NullPinterException.

Вот версия C # для поиска n-го дочернего элемента из списка ссылок.

public Node GetNthLast(Node head, int n)
    {
        Node current, nth;
        current = nth = head;
        int counter = 0;

        while (current.next != null)
        {
            counter++;
            if (counter % n == 0)
            {
                for (var i = 0; i < n - 1; i++)
                {
                    nth = nth.next;
                }
            }
            current = current.next;
        }
        var remainingCounts = counter % n;
        for (var i = 0; i < remainingCounts; i++)
        {
            nth = nth.next;
        }
        return nth;
    }

В зависимости от допуска стоимости памяти (O (k) в этом решении) мы могли бы выделить массив указателей длины k и заполнить его узлами в виде кругового массива при обходе связанного списка.

Когда мы закончим обход связанного списка, первого элемента массива (просто убедитесь, что 0-индекс правильно вычислен, поскольку это круговой массив), мы получим ответ.

Если первый элемент массива равен нулю, наша проблема не решена.

Прежде всего

Как упоминается в комментарии, но для большей ясности, вопрос от:

<Cracking the coding interview 6th> | IX Interview Questions | 2. Linked Lists | Question 2.2.

Это отличная книга Gayle Laakmann McDowell, инженера-программиста из Google, который опросил множество людей.

Подходы

(Предполагая, что связанный список не отслеживает длину), есть 2 подхода в O (n) времени и O (1) пробел:

/**
 * Find k-th element to end of singly linked list, whose size unknown,
 * <p>1-th is the last, 2-th is the one before last,
 *
 * @author eric
 * @date 1/21/19 4:41 PM
 */
public class KthToEnd {
    /**
     * Find the k-th to end element, by find length first.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndViaLen(LinkedListNode<Integer> head, int k) {
        int len = head.getCount(); // find length,

        if (len < k) return null; // not enough element,

        return (Integer) head.getKth(len - k).value; // get target element with its position calculated,
    }

    /**
     * Find the k-th to end element, via 2 pinter that has (k-1) distance.
     *
     * @param head
     * @param k
     * @return
     */
    public static Integer kthToEndVia2Pointer(LinkedListNode<Integer> head, int k) {
        LinkedListNode<Integer> p0 = head; // begin at 0-th element,
        LinkedListNode<Integer> p1 = head.getKth(k - 1); // begin at (k-1)-th element,

        while (p1.next != null) {
            p0 = p0.next;
            p1 = p1.next;
        }

        return p0.value;
    }

    static class LinkedListNode<T> {
        private T value;
        private LinkedListNode next;

        public LinkedListNode(T value) {
            this.value = value;
        }

        /**
         * Append a new node to end.
         *
         * @param value
         * @return new node
         */
        public LinkedListNode append(T value) {
            LinkedListNode end = getEnd();
            end.next = new LinkedListNode(value);
            return end.next;
        }

        /**
         * Append a range of number, range [start, end).
         *
         * @param start included,
         * @param end   excluded,
         */
        public void appendRangeNum(Integer start, Integer end) {
            KthToEnd.LinkedListNode last = getEnd();
            for (int i = start; i < end; i++) {
                last = last.append(i);
            }
        }

        /**
         * Get end element of the linked list this node belongs to, time complexity: O(n).
         *
         * @return
         */
        public LinkedListNode getEnd() {
            LinkedListNode end = this;
            while (end != null && end.next != null) {
                end = end.next;
            }

            return end;
        }

        /**
         * Count of element, with this as head of linked list.
         *
         * @return
         */
        public int getCount() {
            LinkedListNode end = this;
            int count = 0;
            while (end != null) {
                count++;
                end = end.next;
            }

            return count;
        }

        /**
         * Get k-th element from beginning, k start from 0.
         *
         * @param k
         * @return
         */
        public LinkedListNode getKth(int k) {
            LinkedListNode<T> target = this;
            while (k-- > 0) {
                target = target.next;
            }

            return target;
        }
    }
}

import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * KthToEnd test.
 *
 * @author eric
 * @date 1/21/19 5:20 PM
 */
public class KthToEndTest {
    private int len = 10;
    private KthToEnd.LinkedListNode<Integer> head;

    @BeforeClass
    public void prepare() {
        // prepare linked list with value [0, len-1],
        head = new KthToEnd.LinkedListNode(0);
        head.appendRangeNum(1, len);
    }

    @Test
    public void testKthToEndViaLen() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
        }
    }

    @Test
    public void testKthToEndVia2Pointer() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - i);
        }
    }
}