<Problem Link>
<Comment>
Linked-List는 항상 포인터를 다루는 것이 가끔 얼마나 까다로운 것인지 느끼게 해준다.
양방향이라면 상관 없지만 단방향일경우 함부로 연결을 끊으면 원하는 노드를 얻기가 힘들어 질수도 있으므로
항상 제거를 해야한다면, 그 과정이 완벽하게 이루어지기 위해 필요한 노드를 모두 확보했는지 체크해야한다.
이번 문제같은경우가 그렇다.
여기서의 관건은 가장 적은 resource를 사용하여 1회 scan만으로 특정노드를 제거하는 것,
일단은 Leader + Follower 형태로 해결하였는데, 더 좋은 해답이 있을것 같기도 하고,,? ㅎ
<Solution> Python - Accepted
================================================
실행시간 : 64ms
시간복잡도 : O(N)
공간복잡도 : O(1)
================================================
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @return a ListNode
def removeNthFromEnd(self, head, n):
lead = head
follow = head
counter = 0
while lead.next : # LinkedList의 End확인을 위한 leader가 먼저 scan
lead = lead.next
if counter == n : # 제거 노드 바로 이전 노드를 정확히 follow가 가리킨다.
follow = follow.next
else :
counter += 1
if counter == n :
rmNode = follow.next
follow.next = rmNode.next
rmNode.next = None
else :
return head.next
return head
태그 : algorithm, linkedlist