Leetcode-19-Remove Nth Node From End of List

Remove Nth Node From End of List

leetcode: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Description:

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

Idea:

Step1: set the dummy node, and set two pointer, fast pointer is used to traverse and control the range(because it’s the nth node from end), slow pointer is used to point target

Step2: because the nth node from the end, First move the fast pointer to the corresponding position, and then start to move the slow pointer, so that when the fast pointer moves to null, the slow pointer will point to the target

Step3: set the previous node, and in the loop, make it equal to slow pointer firstly, then make slow node move to next node, so the previous node will be the previous node of target

Step4: skip the target node, and make previous node’s next node equal to target node’s next node

Step5: return real list(dummy.next)

Code:

/**
 * 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) {
        //set two pointer, fast pointer is used to traverse and control the range(because it's the nth node from end), slow pointer is used to point target
        ListNode dummy = new ListNode(-1,head);
        ListNode slow = dummy;
        ListNode fast = dummy;
        
        // because the nth node from the end, First move the fast pointer to the corresponding position, and then start to move the slow pointer, so that when the fast pointer moves to null, the slow pointer just points to the target
        //move fast node to corresponding position
        while(n-->0){
            fast = fast.next;
        }
        //set the previous node to record the previous node of the target
        ListNode previous = null;
        //traverse the left list, when the fast is null, slow will be the target, and use previous to record the previous node of slow
        while(fast!=null){
            fast = fast.next;
            previous = slow;
            slow = slow.next;
        }
        //skip the target node
        previous.next = slow.next;
        return dummy.next; 
    }
}