[LeetCode] 876. Middle of the Linked List

- Problem

876. Middle of the Linked List

단일 링크드 리스트가 주어졌을 때, 중간 노드를 구하는 문제이다.

주어진 링크드 리스트의 전체 길이를 파악한다면 문제를 쉽게 해결할 수 있다.

---

- 내 풀이 1

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        size_pointer, size = head, 0
        
        while size_pointer:
            size += 1
            size_pointer = size_pointer.next
        
        for i in range(size//2):
            head = head.next
        
        return head

풀이하자면 다음과 같다.

• 주어진 linked list의 길이를 파악하기 위한 size_pointer를 지정한다.
• 다음 노드가 null 값일 때까지 링크드 리스트를 순회하며 전체 길이를 구한다.
• 링크드 리스트의 절반 길이만큼 head의 포인터를 이동시킨다.

링크드 리스트 노드의 개수가 N이라고 하면, 시간 복잡도는 다음과 같다.

• 사이즈를 파악하기 위해 전체를 순회해야 하므로 O(N)
• 사이즈의 절반 길이만큼 이동시켜야하므로 O(N//2)
• 즉, O(N)이라는 시간 복잡도를 가지게 된다.

공간 복잡도는 상수인 size만 있으므로 O(1)이다.

이 문제를 해결하는 또 다른 접근법이 있다.

---

- 내 풀이 2

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        faster = head
        
        while faster and faster.next:
            head = head.next
            faster = faster.next.next
        
        return head

• faster 는 하나의 반복 당 2개씩 이동한다.
• head는 하나의 반복 당 1개씩 이동한다.
• faster가 링크드 리스트의 끝에 도달한다면, head는 N/2 노드를 이동했을 것이다.
• 이 때, head를 리턴한다.

누추하지만 시각적인 이해를 돕자면...

   H(head)
1️⃣ 1 -> 2 -> 3 -> 4 -> 5
   F(faster)

	    H
2️⃣ 1 -> 2 -> 3 -> 4 -> 5
	         F

   		     H
3️⃣ 1 -> 2 -> 3 -> 4 -> 5
	 				   F
                       
F가 끝에 도달하면 faster.next가 존재하지 않으므로 조건문을 탈출한다.

   H(head)
1️⃣ 1 -> 2 -> 3 -> 4 -> 5 -> 6
   F(faster)

	    H
2️⃣ 1 -> 2 -> 3 -> 4 -> 5 -> 6
	         F

   		     H
3️⃣ 1 -> 2 -> 3 -> 4 -> 5 -> 6
	 				   F

				  H
4️⃣ 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
								  F

faster가 null이 되므로 조건문을 탈출한다.

시간 복잡도 O(N)을 만족한다. (정확히는 O(N/2))

---

- 결과