[LeetCode] 876. Middle of the Linked List

말하는 감자·2024년 12월 4일

algorithm data structure leetcode linked list python two pointer 리트코드 알고리즘 연결 리스트 자료구조 코딩테스트 코딩테스트 준비 투 포인터 파이썬

LeetCode

목록 보기

23/32

오늘 문제는 이전까지 푼 연결 리스트 문제들전에 풀었다면 도움이 됐을 문제입니다.

1. 오늘의 학습 키워드

Linked List
Tow Pointer

2. 문제: 876. Middle of the Linked List

단계: Easy
주제: Linked List, Two Pointers
출처: https://leetcode.com/problems/middle-of-the-linked-list/description/?envType=problem-list-v2&envId=linked-list&difficulty=EASY

Description

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

The number of nodes in the list is in the range [1, 100].
1 <= Node.val <= 100

3. 문제 풀이

Step1. 문제 이해하기

링크드 리스트가 주어졌을 때, 주어진 링크드 리스트의 중간 노드를 반환하는 문제입니다.

최근에 연결 리스트 문제를 정말 많이 풀고 있는데요. 거기서 나오는 문제들을 풀 때 사용했던 기술들을 활용한다면 금방 풀 것 같습니다.

입출력을 살펴보겠습니다.

Input:
- 주어지는 연결 리스트의 노드 개수는 1이상 100이하입니다.
- 빈 리스트인 경우는 없습니다. 또한, 시간 복잡도는 정말 여유롭습니다.
Output:
- 중간 노드를 반환합니다. 반환값의 타입은 Optional[ListNode]이므로 연결 리스트를 순회하면서 중간 위치에 오면 리턴하면 될 것 같습니다.

Step2. 문제 분석하기

문제는 간단합니다. 주어진 연결 리스트의 가운데 노드를 반환하면 해결되는 문제입니다.

그렇다면 이전 펠린드롬인지를 판별하는 문제가 기억나시나요? 절반까지 오고 나머지 절반을 뒤집어서 두 개를 비교하는 문제가 있었습니다. 해당 문제에서 투 포인터를 통해 절반까지 연결 리스트를 순회를 했었습니다. 이 방법을 활용한다면 금방 문제가 해결될 것으로 보입니다.

바로 코드 설계를 진행해보도록 하겠습니다.

Step3. 코드 설계

투 포인터를 활용하여 연결 리스트 중간까지 탐색
1. 한 칸씩 이동하는 포인터, 두 칸씩 이동하는 포인터를 지정
- slow pointer(s)는 한 번에 한 칸씩 이동합니다.
- fast pointer(f)는 한 번에 두 칸씩 이동합니다.
- 따라서 f는 s보다 두 배 빠르게 리스트를 순회합니다.
- Fast가 끝에 도달하면 Slow는 중간에 위치
  - f가 리스트의 끝에 도달했을 때:
    - s는 리스트의 중간에 위치하게 됩니다.
  - 예를 들어:
    - 리스트 길이가 n이라면, f는 2씩 이동하기 때문에 n/2 단계에서 끝에 도달합니다.
    - 그 동안 s는 n/2번 이동하며 중간에 도달합니다.

Step4. 코드 구현

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution(object):
    def middleNode(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        s, f = head, head
        while f and f.next:
            s = s.next
            f = f.next.next
        return s

코드 설명:
- 포인터 초기화:
  - Slow 포인터(s)와 Fast 포인터(f)를 head로 초기화합니다.
  - 이 두 포인터를 활용해 리스트를 탐색하며 중간 지점을 찾습니다.
- 반복문:
  - f와 f.next가 존재할 동안 반복합니다.
  - s는 한 번에 한 칸씩 이동하며, s = s.next로 업데이트됩니다.
  - f는 한 번에 두 칸씩 이동하며, f = f.next.next로 업데이트됩니다.
  - Fast 포인터가 끝에 도달했을 때 Slow 포인터는 리스트의 중간 지점에 도달합니다.
- 중간 노드 반환:
  - Fast 포인터가 리스트 끝에 도달하거나 끝을 넘어가면, Slow 포인터 s는 중간 노드를 가리키게 됩니다.
  - Slow 포인터가 가리키는 노드를 반환합니다.
시간 복잡도: $O(n)$
리스트의 길이에 비례하여 Fast 포인터가 리스트를 한 번 순회하기 때문에, 시간 복잡도는 $O(n)$ 입니다.
결과: https://leetcode.com/problems/middle-of-the-linked-list/submissions/1469832333