Welcome to Subscribe On Youtube

Question

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

19	Remove Nth Node From End of List

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

For example,

   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.

Note:
Given n will always be valid.
Try to do this in one pass.

@tag-linkedlist

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

Java

  • 
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;
	    }
	}

}

  • // 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

All Problems

All Solutions