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

Question

Я практикую Python, и я не мог придумать никакого решения этой проблемы.Проблема состоит в том, чтобы удалить k-й последний элемент из односвязного списка за один проход и постоянное пространство.Я могу думать только о решении, которое требует 2 прохода.Кроме того, в вопросе размер списка не был упомянут, поэтому я предполагаю, что размер известен априори.Кто-нибудь может показать мне способ сделать это за один проход, пожалуйста?

Answer 1

Если размер известен, то вы хотите удалить элемент s - kth.

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

Answer 2

Кэшируйте указатель / местоположение элемента перед элементом, который нужно удалить, во временной переменной по мере продвижения.

Таким образом, будет один цикл, повторяющийся до конца.Было бы утверждение, что кэширует (ik-1) -й элемент в temp.

Когда этот цикл завершится, у temp будет местоположение удаляемого элемента.

Надеюсь, это поможет.

Answer 3

От GeeksforGeeks

Метод 2 (используйте два указателя)

Ведение двух указателей - указатель ссылки и главный указатель. Инициализируйте и ссылку, и главные указатели на голову. Сначала переместите ссылочный указатель на n узлов из головы. Теперь переместите оба указатели один за другим, пока указатель ссылки не достигнет конца. Сейчас главное указатель будет указывать на n-й узел с конца. Вернуть основной указатель.

Доступна реализация на python.