728x90
마지막 노드부터 시작하여 인자값으로 주어진 노드를 빼고 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.
'Programming > LeetCode' 카테고리의 다른 글
[LeetCode] #1290 Convert Binary Number in a Linked List to Integer (repeat : 0) (0) | 2024.01.12 |
---|---|
[LeetCode] #83 Remove Duplicates from Sorted List (repeat : 0) (0) | 2024.01.11 |
[LeetCode] #86 partition List (repeat : 0 ) (0) | 2024.01.07 |
[LeetCode] #141 Linked List Cycle (repeat:1) (0) | 2023.12.25 |
[LeetCode] #876 Middle of the Linked List (repeat:0) (0) | 2023.12.24 |