19. Remove Nth Node From End of List (Medium)


Given a linked list, remove the n-th node from the end of list and return its head.


Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.


Given n will always be valid.

Follow up:

Could you do this in one pass?


class Solution {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode ptr1 = head;

        int count = 0;
        while (count < n) {
            ptr1 = ptr1.next;

            // if n >= the length of given list, return the node next to head
            if (ptr1 == null) {
                return head.next;


        // To reach here, the reversed nth node can't be the head node

        // Move one more step, now ptr1 is at node n + 1.
        ptr1 = ptr1.next;

        ListNode ptr2 = head;

        // ptr1 moves x-n-1 steps to reach the end. At the same time, ptr2 move x-n-1
        // steps from the head, the index becomes x-(x-n-1)=n+1 counting from the tail. It's
        // easy to get the nth node in reverse order which is the next value of node
        // n+1(reversed index).

        while (ptr1 != null) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;

        ptr2.next = ptr2.next.next;

        return head;

Incorrect Solutions


Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-02-26 11:32:47

results matching ""

    No results matching ""