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