This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is LeetCode 19. Deleting the NTH node from the list is medium difficulty.

Tag: linked list, fast and slow pointer, double pointer

Given a linked list, delete the NTH node from the bottom of the list and return the head of the list.

Advanced: Can you try using a scan implementation?

Example 1:

Input: head = [1,2,3,4,5], n = 2Copy the code

Example 2:

Input: head = [1], n = 1 output: []Copy the code

Example 3:

Input: head = [1,2], n = 1Copy the code

Tip:

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

How fast a pointer

To delete the penultimate NTH node of a linked list, first determine the position of the penultimate NTH node.

We can set two Pointers, slow and fast, to start at head.

Then let fast move forward n steps, slow pointer does not move, at this time the distance between the two Pointers is N.

Slow and FAST go forward at the same time (holding the same distance between them) until the fast pointer reaches the end position.

At this point slow stops in front of the node to be deleted, making slow.next = slow.next-next.

However, there is a boundary case that needs to be noted here: if the length of the list is L and we happen to delete the last L node (delete the head node), then fast will become null after n steps forward, and we just need to make head = slow. Next to delete.

Code:

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;
        while (n-- > 0) fast = fast.next;
            
        if (fast == null) {
            head = slow.next;
        } else {
            while(fast.next ! =null) {
                slow = slow.next;
                fast = fast.next;
            }
            slow.next = slow.next.next;
        }
        returnhead; }}Copy the code
  • Time complexity: The length to be scanned is the length of the linked list. The complexity is O(n)O(n)O(n)
  • Space complexity: O(1)O(1)O(1)

The last

This is the 19th article in our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions in LeetCode, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.