Java one pass solution with inline explaination


  • 0
    S
    public class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            // as head can't be changed, use a ptr to iterate through the list
            ListNode ptr = head;
            // prev is n+1th from the end, current is nth from the end
            ListNode prev = null, current = null;
            // have a count for position
            int count = 0;
            // iterate till the end of the list
            while (ptr != null) {
                // update count (it has to be the first step as the nth position is 1 based)
                count++;
                // this is the case when the head is nth from the ptr
                if (count == n) {
                    current = head;
                }
                // this is the case when the head is n+1th from the ptr
                else if (count == n+1) {
                    prev = head;
                    current = current.next;
                }
                // when the list is long enough, just keep updating prev and current
                else if (count > n+1) {
                    current = current.next;
                    prev = prev.next;
                }
                ptr = ptr.next;
            }
            // prev could be empty in some cases, use head instead
            if (prev == null) {
                head = current.next;    // (no need to worry about empty current)
            } else {
                prev.next = current.next;
            }
            // return unchanged head
            return head;
        }
    }
    

Log in to reply
 

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