Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/19.html

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

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

Constraints:

  • The number of nodes in the list is sz.
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

 

Follow up: Could you do this in one pass?

Algorithm

The problem requires a single traversal to solve the problem, so you have to think of some more clever ways. For example, the first thing to consider is how to find the Nth node from the bottom. Since only one traversal is allowed, a complete traversal cannot be used to count the number of elements in the linked list. Instead, it should be removed after traversing to the corresponding position.

So you need to use two pointers to help solve the problem, pre and cur pointers. First, the cur pointer moves forward by N steps. If cur points to empty at this time, indicating that N is the length of the linked list, the first element that needs to be removed is the first element. Then return head->next at this time. If cur exists, continue to Go down, at this time the pre pointer also follows, until cur is the last element and stop, at this time pre points to the previous element of the element to be removed, and then modify the pointer to skip the element to be removed

Code

  • 
    public class Remove_Nth_Node_From_End_of_List {
    
    	public static void main(String[] args) {
    
    	}
    
    	/**
    	 * Definition for singly-linked list.
    	 * public class ListNode {
    	 *     int val;
    	 *     ListNode next;
    	 *     ListNode(int x) { val = x; }
    	 * }
    	 */
    	public class Solution {
    	    public ListNode removeNthFromEnd(ListNode head, int n) {
    
    	        ListNode nBehindPrev = new ListNode(0);
    	        ListNode nBehind = head;
    	        nBehindPrev.next = nBehind;
    
    	        ListNode headPrev = nBehindPrev;
    	        headPrev.next = head;
    
    	        ListNode current = head;
    
    	        // nBehind starts moving after n steps of current
    	        //    Given linked list: 1->2->3->4->5, and n = 2.
    	        int count = 0;
    	        while (current != null) {
    	            if (count >= n) {
    	                nBehindPrev = nBehindPrev.next; // note order
    	                nBehind = nBehind.next;
    	            }
    
    	            current = current.next;
    	            count++;
    	        }
    
    	        // cut
    	        nBehindPrev.next = nBehind.next;
    	        nBehind.next = null; // maybe not required, both pointing to nBehind.next
    
    	        return headPrev.next;
    	    }
    	}
    
    	public class Solution_2Scan {
    
    		// actually it's scanning twice
    	    public ListNode removeNthFromEnd_refactor(ListNode head, int n) {
    	        if(head == null) {
    	            return head;
    	        }
    
    	        // move first node to desired position first, avoid flag and count etc.
    	        int count = 0;
    	        ListNode current = head;
    	        while(count < n) {
    	            count++;
    	            current = current.next;
    	        }
    
    	        ListNode dummy = new ListNode(0);
    	        dummy.next = head;
    
    	        ListNode toDelete = head;
    	        ListNode toDeletePrev = dummy;
    
    	        while(current != null) {
    
    	            current = current.next;
    
    	            toDelete = toDelete.next;
    	            toDeletePrev = toDeletePrev.next;
    
    	        }
    
    	        // remove the one
    	        toDeletePrev.next = toDelete.next;
    
    	        // return head;
    	        return dummy.next;
    	    }
    
    
    	    public ListNode removeNthFromEnd(ListNode head, int n) {
    	        if(head == null) {
    	            return head;
    	        }
    
    	        ListNode dummy = new ListNode(0);
    	        dummy.next = head;
    
    	        // @note: key is the initialization. at first I set null,
    	        // but if null and input only one node, cannot enter while loop and below 2 variables stay null
    	        ListNode toDelete = head;
    	        ListNode toDeletePrev = dummy;
    
    	        boolean flag = false;
    	        int count = 0;
    	        ListNode current = dummy;
    	        while(current != null) {
    
    	            if(count > n && !flag) {
    	                flag = true;
    	                toDelete = head;
    	                toDeletePrev = dummy;
    	            }
    
    	            current = current.next;
    
    	            if(flag) {
    	                toDelete = toDelete.next;
    	                toDeletePrev = toDeletePrev.next;
    	            }
    
    	            count++;
    	        }
    
    	        // remove the one
    	        toDeletePrev.next = toDelete.next;
    
    	        // return head;
    	        return dummy.next;
    	    }
    	}
    
    }
    
    ############
    
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            ListNode dummy = new ListNode(0, head);
            ListNode fast = dummy, slow = dummy;
            while (n-- > 0) {
                fast = fast.next;
            }
            while (fast.next != null) {
                slow = slow.next;
                fast = fast.next;
            }
            slow.next = slow.next.next;
            return dummy.next;
        }
    }
    
  • // OJ: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
            ListNode *p = head, *q = head;
            while (n--) q = q->next;
            if (!q) return head->next;
            while (q->next) {
                p = p->next;
                q = q->next;
            }
            p->next = p->next->next;
            return head;
        }
    };
    
  • # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
            dummy = ListNode(next=head)
            fast = slow = dummy
            for _ in range(n):
                fast = fast.next
            while fast.next:
                slow, fast = slow.next, fast.next
            slow.next = slow.next.next
            return dummy.next
    
    ############
    
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
      def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head
        fast = slow = dummy
    
        while n and fast:
          fast = fast.next
          n -= 1
    
        while fast.next and slow.next:
          fast = fast.next
          slow = slow.next
    
        slow.next = slow.next.next
        return dummy.next
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func removeNthFromEnd(head *ListNode, n int) *ListNode {
    	dummy := &ListNode{0, head}
    	fast, slow := dummy, dummy
    	for ; n > 0; n-- {
    		fast = fast.Next
    	}
    	for fast.Next != nil {
    		slow, fast = slow.Next, fast.Next
    	}
    	slow.Next = slow.Next.Next
    	return dummy.Next
    }
    
  • /**
     * Definition for singly-linked list.
     * class ListNode {
     *     val: number
     *     next: ListNode | null
     *     constructor(val?: number, next?: ListNode | null) {
     *         this.val = (val===undefined ? 0 : val)
     *         this.next = (next===undefined ? null : next)
     *     }
     * }
     */
    
    function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
        const dummy = new ListNode(0, head);
        let fast = dummy;
        let slow = dummy;
        while (n--) {
            fast = fast.next;
        }
        while (fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
    
    
  • /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} n
     * @return {ListNode}
     */
    var removeNthFromEnd = function (head, n) {
        const dummy = new ListNode(0, head);
        let fast = dummy,
            slow = dummy;
        while (n--) {
            fast = fast.next;
        }
        while (fast.next) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    };
    
    
  • # Definition for singly-linked list.
    # class ListNode
    #     attr_accessor :val, :next
    #     def initialize(val = 0, _next = nil)
    #         @val = val
    #         @next = _next
    #     end
    # end
    # @param {ListNode} head
    # @param {Integer} n
    # @return {ListNode}
    def remove_nth_from_end(head, n)
      dummy = ListNode.new(0, head)
      fast = slow = dummy
      while n > 0
          fast = fast.next
          n -= 1
      end
      while fast.next
          slow = slow.next
          fast = fast.next
      end
      slow.next = slow.next.next
      return dummy.next
    end
    
  • // Definition for singly-linked list.
    // #[derive(PartialEq, Eq, Clone, Debug)]
    // pub struct ListNode {
    //   pub val: i32,
    //   pub next: Option<Box<ListNode>>
    // }
    //
    // impl ListNode {
    //   #[inline]
    //   fn new(val: i32) -> Self {
    //     ListNode {
    //       next: None,
    //       val
    //     }
    //   }
    // }
    impl Solution {
        pub fn remove_nth_from_end(head: Option<Box<ListNode>>, n: i32) -> Option<Box<ListNode>> {
            let mut dummy = Some(Box::new(ListNode { val: 0, next: head }));
            let mut slow = &mut dummy;
            let mut fast = &slow.clone();
            for _ in 0..=n {
                fast = &fast.as_ref().unwrap().next;
            }
            while fast.is_some() {
                fast = &fast.as_ref().unwrap().next;
                slow = &mut slow.as_mut().unwrap().next;
            }
            slow.as_mut().unwrap().next = slow.as_mut().unwrap().next.as_mut().unwrap().next.take();
            dummy.unwrap().next
        }
    }
    
    

All Problems

All Solutions