문제
Given a linked list, remove the n-th node from the end of list and return its head.
풀이
어떤 node를 지우기 위해선 그 노드의 앞 node를 알아야한다.
head node는 앞 node가 없기 때문에, 임시로 prev node를 만들어서 앞에 붙여준다.
그 후, 두개의 포인터를 관리하는데, 서로 차이가 n+1만큼 떨어지게 관리한다.
이렇게 하면 앞쪽 포인터가 NULL에 도착했을 때, 뒷쪽포인터는 지워야할 node의 앞 node를 가리키게 된다.
따라서 뒷쪽포인터를 이용하여, 삭제작업을 진행하면 된다.
Time Complexity : $O(n)$
코드
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode * prev = new ListNode(0);
prev->next=head;
ListNode * n1= prev;
ListNode * n2= prev;
for(int i=0;i<=n;i++) n2=n2->next;
while(n2)
{
n1=n1->next;
n2=n2->next;
}
ListNode * d = n1->next;
n1->next=n1->next->next;
delete d;
return prev->next;
}
};
'PS > leetcode' 카테고리의 다른 글
[leetcode] 21. Merge Two Sorted Lists (0) | 2019.04.29 |
---|---|
[leetcode] 20. Valid Parentheses (0) | 2019.04.29 |
[leetcode] 18. 4Sum (0) | 2019.04.29 |
[leetcode] 17. Letter Combinations of a Phone Number (0) | 2019.04.29 |
[leetcode] 16. 3Sum Closest (0) | 2019.04.29 |