[Leetcode][Python] 19. Remove Nth Node From End of List

리트코드 / 파이썬 / 19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

 

Remove Nth Node From End of List - LeetCode

풀이 방법

linkedlist를 한번에 순회하면서 찾는 방법

-> 맨 앞에 dummy 노드부터 시작. fast가 먼저 N만큼 가고, 그 후 slow와 fast를 fast.next == None일 때까지 순회한다.

-> 그럼 slow가 가리키는 노드의 next를 slow.next.next로 바꿔주면 원하는 노드가 삭제된다.

 

 

#case 1: N=2이므로 맨 처음 fast가 2까지 가고, 그다음 slow, fast가 각각 3, 5까지 이동한다. 

 

 

 

#case 2: N=2이므로 맨 처음 fast가 2까지 가고, fast.next가 더이상 없으므로 slow는 이동하지 않는다.

 

 

 

#case 3: N=3이므로 맨 처음 fast가 3까지 가고, fast.next가 없을때까지 이동하면 slow는 4, fast는 7까지 이동한다.

 

이렇게 linked list가 주어지고, 끝에서부터 k번째에서 무언가 해주어야 하는 경우..

위와 같이 fast, slow 사이의 거리를 k만큼 유지시키면서 원하는 작업을 해주면 된다. 

 

List를 한 번 순회하므로 복잡도는 O(L)이다. (L: 연결리스트의 길이)

 

소스 코드

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head

        slow = fast = dummy

        for i in range(n):
            fast = fast.next

        while fast.next:
            slow = slow.next
            fast = fast.next

        slow.next = slow.next.next

        return dummy.next