Leetcode 19. Remove Nth node from end of the list (Linked List, two-pointer)

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

Remove Nth Node From End of List - LeetCode

 

---

 

처음 풀이)

# 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]:
        lgh, curr = self.length(head), head
        
        if lgh == n:
            return head.next
        
        for i in range(lgh-n-1):
            curr = curr.next
        curr.next = curr.next.next          
        return head
    
    def length(self,head):
        temp = head
        cnt = 0
        while temp:
            cnt +=1
            temp = temp.next
        return cnt

처음에 문제를 풀이한 방식은 따로 length함수를 만들어서, 

Linkedlist의 길이를 카운팅하도록 한뒤,

원래 리스트에서 해당 N번째 인덱스만큼 이동하도록 해서 이전의 노드와 그 다음다음의 노드를 이어 붙여주는 식으로

구성했습니다. 이 방법도 틀린건 아니지만, 다른 분들의 풀이를 보면서 다양한 풀이법을 분석해봤는데요

 

---

One-Pointer, Two-Pass method)

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
	ptr, length = head, 0
	while ptr:
		ptr, length = ptr.next, length + 1
	if length == n : return head.next
	ptr = head
	for i in range(1, length - n):
		ptr = ptr.next
	ptr.next = ptr.next.next
	return head

 

전체적인 풀이는 제가 푼 방식과 동일하지만, 따로 def를 만들지 않고 내부에 만들어서

훨씬 간결하게 코드를 구성했습니다

 

---

 

Two-Pointer, One-Pass method)

이 방법은 역발상 적으로 끝에서 n 번째라는 요소를 두개의 포인터간의 간격으로 재해석한 방법인데요

fast 포인터를 먼저 출발 시키고 n만큼 갔을 때 slow를 출발시킨 뒤,

fast가 마지막 노드에 도달하면 자연스럽게 slow 포인터는 끝에서 n번째에 위치한 노드가 됩니다!

 

def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
	fast = slow = head
	for i in range(n):
		fast = fast.next
	if not fast: return head.next
	while fast.next:
		fast, slow = fast.next, slow.next
	slow.next = slow.next.next
	return head

 

풀이를 보고 어떻게 이런 생각을 했지?! 싶었는데요, 역시 오늘도 배워갑니다

코드 자체 구성도 간결하게 fast노드를 n만큼 이동시키고

fast를 예외처리 한뒤에 while문에 fast.next가 null이 되기 직전까지 작동되도록 한뒤에

slow와 fast를 동시에 다시 작동시킵니다.

 

세상에는 참 재밌고 신기한 코드가 많은거 같습니다 ㅎㅎㅎㅎ