[LeetCode] #9 Remove Nth Node From End of List (repeat:0)

마지막 노드부터 시작하여 인자값으로 주어진 노드를 빼고 head를 리턴하는 문제이다. 

 

# Description

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

 

 

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

 

 

#Solution 

class Solution{
	public ListNode removeNthFromEnd(ListNode head,int n){
    
    	ListNode dummy = new ListNode(0,head); //initialize the ListNode with value 0 pointing to the head node 
        ListNode slow = dummy; //initialize slow pointer at head
        ListNode fast = head; //initialize fast pointer at head
        
        while(n>0){ //move fast pointers nth steps ahead
        	fast = fast.next;
            n -=1;
        }
        
        while(fast != null){ //iterates till the fast reaches null
        	slow = slow.next;
            fast = fast.next; // here, fast returns null so i returned slow
        }
        
        slow.next = slow.next.next; // set slow pointer points to the next pointer
        
        return dummy.next; //dummy node's value is 0, therefore points to dummy.next 
       						 //which points to the head
    }
}

I think the key to solve this problem is to make slow pointer to skip the nth node and replace to the next node of the nth node

therefore I used slow.next = slow.next.next

In terms of time complexity , I think the time complextiy is both O(n) because in while loop,  fast and slow pointers iterates n number of times  . O(n) time 

In terms of space complexity , It is O(1) constant running time because this algorithm uses only two constant number of pointers which is slow and fast.