화물 열차 앞뒤 무게 쏠림

문제

화물 열차의 각 칸이 단일 연결 리스트로 이어져 있습니다. head는 맨 앞 칸이고, 각 노드의 val은 그 칸에 실린 화물의 무게(t)입니다.

기관사는 열차가 앞쪽으로 쏠렸는지 뒤쪽으로 쏠렸는지 확인하려 합니다. 열차를 앞 절반과 뒤 절반으로 나누되, 칸 수가 홀수라면 가운데 칸은 뒤 절반에 포함시킵니다. 즉 칸이 n개면 앞 절반은 floor(n / 2)칸입니다.

head가 주어질 때 (앞 절반 무게 합) − (뒤 절반 무게 합) 을 반환하는 solution(head) 함수를 작성하세요. 값이 양수면 앞쪽이, 음수면 뒤쪽이 더 무겁다는 뜻입니다.

예시

제약 조건

• 칸 수 n: 0 ≤ n ≤ 100,000 (n = 0이면 0을 반환합니다)
• 0 ≤ Node.val ≤ 10,000
• 리스트 길이를 미리 알 수 없으며, 리스트를 한 번만 훑고 풀 수 있습니다.

시간 복잡도 목표: O(n)

공간 복잡도 목표: O(1)