[Python] 876. Middle of the Linked List

The LeetCode Beginner's Guide의 Challenge Problems에서 5번째로 나온 문제.

 

Linked list의 가운데 node를 리턴하라는 내용인데,

node라는 개념을 얼추 이해하기만 한

비전공자인 나에게는 다소 생소한 개념이었다.

 

처음에는 일반적인 list인 줄 알고 len()으로 linked list의 길이를 내려고 했으나,

linked list에는 그런 것은 안 통한다고 한다.

# 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):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        n = 0
        nhead = head
        while nhead.next:
            nhead = nhead.next
            n += 1
        
        half = n//2 + n%2
        while half > 0:
            head = head.next
            half -= 1
        
        return head

* linked list에 관해 잘 아는 게 아니라 설명이 부정확할 수 있습니다!

1. head로 nhead를 지정

2. head를 하나씩 옆 node로 가면서 수를 1씩 더하여 길이(n) 확인

3. half 값이 0이 될때까지 node를 옆으로 밀기

 

그 외에 다른 풀이법도 있어, 소개하고자 한다.

# 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]
        """
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow

1. slow와 fast를 각각 head로 잡고

2. 'while fast and fast.next'로 fast와 fast.next 둘 다 None이 아닐 때까지 반복하기

3. slow는 1 node, fast는 2 node 앞으로 이동

4. linked lint에 fast가 도달하면, slow는 list의 중간 지점에 도착