LeetCode [876]: Middle of the Linked List

📌 LeetCode [876]: Middle of the Linked List

🔗 문제 링크

---

문제 설명 📄

단일 연결 리스트의 헤드 head가 주어집니다.
리스트의 중간 노드를 반환하세요.
리스트의 길이가 짝수라면, 두 번째 중간 노드를 반환해야 합니다.

---

문제 접근 방식 📋

1. 리스트 길이 계산:
   • 리스트를 한 번 순회하며 전체 길이를 계산.
2. 중간 위치 탐색:
   • 길이의 절반만큼 다시 순회하여 중간 노드에 도달.
3. 중간 노드 반환:
   • 중간에 도달한 노드를 반환.

---

Solution 💻

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = head
        length = 0
        while temp:
            length += 1
            temp = temp.next

        for _ in range(length // 2):
            head = head.next

        return head

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 리스트를 두 번 순회: 첫 번째 순회로 길이를 계산, 두 번째 순회로 중간 노드 탐색.

공간 복잡도 분석 🗄️

• 공간 복잡도: (O(1))
  • 추가 메모리 사용 없이 노드 포인터만 이동.

---

리팩토링 🛠️

개선된 코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

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

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: (O(n))
  • 리스트를 한 번 순회하여 중간 노드를 탐색.

리팩토링 후 공간 복잡도 🗄️

• 공간 복잡도: (O(1))
  • 두 개의 포인터만 사용.

---