문제
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]Constraints:
The number of nodes in the list is sz.
- 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
문제 접근하기
투 포인터를 사용해서 제거해야 하는 노드에 접근하려고 했다.
초기에 left와 right를 각각 0과 head로 설정한다.
right 포인터를 n만큼 먼저 이동시킨 후, left와 right를 동시에 이동시킨다. 이렇게 하면 두 포인터가 일정한 거리를 두고 동시에 이동할 수 있게 되어, right가 끝에 도달할 때 left는 삭제해야 할 노드 바로 앞을 가리키게 된다.
이 후, left의 next를 left.next.next로 덮어씌워준다.
위와 같은 방식을 코드로 풀어내면
코드 작성하기
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy=ListNode(0,head)
left,right=dummy,head
for _ in range(n):
right=right.next
while right:
left=left.next
right=right.next
left.next=left.next.next
return dummy.next투 포인터를 활용하여 문제를 해결하니, 리스트를 한 번 순회하기 때문에 시간 복잡도는 O(sz)이고, 공간 복잡도는 O(1)이다. 이 방식은 추가적인 공간을 사용하지 않고도 효율적으로 문제를 해결할 수 있었다!
