LeetCode 풀기 - 876. Middle of the Linked List

876. Middle of the Linked List

https://leetcode.com/problems/middle-of-the-linked-list/

Middle of the Linked List - LeetCode

문제)

솔루션1)

walker and runner 테크닉을 사용한다.

runner는 2 steps로 이동, walker는 1 step로 노드를 이동한다.

runner가 마지막 위치에 도달했다는 것은 walker가 중간 노드에 위치했다는 것을 의미한다.

 

시간 복잡도 : O(N)

공간 복잡도 : O(1)

 

walk and runner technique

# 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]:
        walker = head
        runner = head
        
        while runner and runner.next:
            # 1 step
            walker = walker.next
            
            # 2 step
            runner = runner.next.next
        
        return walker