[LeetCode] 876. Middle of the Linked List

문제

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.

singly linked list가 주어졌을 때 linked list의 가운데 노드를 반환하세요.
만약 두개의 중간 노드가 있을경우 두번째 노드를 반환하세요.

 

풀이

1. Counting element

알고리즘

Linked List의 노드 개수를 구한 다음, 가운데 인덱스의 Node를 찾는 방법입니다.

class Solution(object):
    def middleNode(self, head):
        node = head
        size = 0
        while(node.next != None):
            node = node.next
            size += 1
        
        mid = int(size / 2)
        if(size % 2 != 0):
            mid += 1

        count = 0
        while(count < mid):
            head = head.next
            count += 1

        return head

 

복잡도

• 시간 복잡도: O(n) + O(n/2)
• 공간 복잡도: O(1)

 

2. Slow and Fast pointer

알고리즘

두칸식 순회하는 Fast와 한칸씩 순회하는 Slow를 사용하는 방법입니다.

Fast가 순회를 다 끝냈으면 Slow의 위치는 중간이라는 점을 이해하시면 됩니다.

class Solution(object):
    def middleNode(self, head):
        slow = head
        fast = head
        while(fast != None and fast.next != None):
            slow = slow.next
            fast = fast.next.next

        return slow

 

복잡도

• 시간 복잡도: O(n)
• 공간 복잡도: O(1)