Simple Java solution in one pass


  • 174
    T

    A one pass solution can be done using pointers. Move one pointer fast --> n+1 places forward, to maintain a gap of n between the two pointers and then move both at the same speed. Finally, when the fast pointer reaches the end, the slow pointer will be n+1 places behind - just the right spot for it to be able to skip the next node.

    Since the question gives that n is valid, not too many checks have to be put in place. Otherwise, this would be necessary.

    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode start = new ListNode(0);
        ListNode slow = start, fast = start;
        slow.next = head;
        
        //Move fast in front so that the gap between slow and fast becomes n
        for(int i=1; i<=n+1; i++)   {
            fast = fast.next;
        }
        //Move fast to the end, maintaining the gap
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        //Skip the desired node
        slow.next = slow.next.next;
        return start.next;
    }

  • 1
    S

    So brilliant!


  • 4
    B

    may I know why fast.next in the for loop is not null? since start.next = null.


  • 4
    V

    Here a new node with value 0 is added in the beginning of the linked list.

    initially fast and slow are pointing to start and "slow.next=head" will change the start.next to head (because at this time start,slow and fast all are pointing to the same node in the linked list).

    Hope this clears your doubt.


  • 25
    U

    In my opinion, this is not a valid solution.
    Supposing the length of this list is l, this solution will visit the previous (l-n) elements twice, which has no difference with first getting the length of this list and in the SECOND pass find the index of the node to delete.


  • 2
    A

    it is impossible to find a solution in one pass unless the length of the list is known upfront.


  • 1
    Z
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Solve [1] 1
        if (head.next == null) {
            return null;
        }
        // Solve [1,2] 1, or [1,2] 2 or [1,2,3] 2, or [1,2,3,4,5] 2
        int counter = 1;
        ListNode start = new ListNode(0);
        start.next = head;
        ListNode fast = start;
        ListNode slow = start;
        while (fast.next != null) {
            fast = fast.next;
            if (counter <= n) {
                counter++;
            } else {
                slow = slow.next;
            }
        }
        slow.next = slow.next.next;
        return start.next;
    }
    

    This solution is essentially the same with the original solution in this post, but without the for loop. So now, people can understand that it IS a one pass solution.


  • 18
    P

    Easier to understand

    public class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
           ListNode newHead = new ListNode(0);
           newHead.next = head;
           ListNode p = newHead;
           ListNode runner = newHead;
           while(n>0){
               runner = runner.next;
               n--;
           }
           while(runner.next!=null){
               runner = runner.next;
               p=p.next;
           }
           p.next = p.next.next;
           return newHead.next;
        }
        
    }

  • 1
    E

    Why not directly return the original head since newHead.next = head?


  • 3
    P

    Because head may have been removed.


  • 0
    E

    I tried "return head;" but it returned the original linked list. I'm wondering where the "delete" is operating.


  • 0
    P

    If you return head, it will failed some tests. e.g. A list has only one Node and will delete it later.


  • 0
    E

    Got it! Thanks!


  • 0
    D

    You misunderstand sth.....


  • 0
    U

    so what's the point of this problem?I think this problem is meaninglesss


  • 2
    A

    Yes. The problem is meaningless. The funny thing is your answer is the one which is close to being correct. But it has just one upvote.
    Two pointer technique is a good technique which can be used in other places like finding cycle in the list. But this problem is particularly worded to force people to think that two pointer technique can give the answer in one pass.


  • 0
    D

    Line 18: java.lang.NullPointerException when input is [1] ,2


  • 1
    S

    your n is invalid


  • 0

    I have try to implement your idea without using the dummy-head node but failed. I think it is really tricky whether to use the dummy-head node. As we may delete the head node 2333333


  • 0
    O

    Actually statement for moving fast pointer:
    the condition should be i<n+1, not i<=n+1
    it will cover all cases!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.