[LeetCode OJ] Remove Nth Node From End of List - Easy Algorithm

<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




통계 위젯 (블랙)

00
0
0

GoogleAdsenseResponsive

Cluster map