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.
@taglinkedlist
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 singlylinked 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/removenthnodefromendoflist/ // 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 singlylinked 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 singlylinked 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