[LinkedLists: Fast and Slow Pointers] 2130. Maximum Twin Sum of a Linked List ★★★

2130. Maximum Twin Sum of a Linked List

 

Reverse 뒤집은 노드 만들기

curr = head          # 원래 리스트의 시작
prev = None          # 뒤집힌 리스트의 시작 (처음엔 없음)

while curr:
    next = curr.next     # 다음 노드 기억
    curr.next = prev     # 현재 노드의 방향을 뒤집음
    prev = curr          # prev를 현재 노드로 업데이트
    curr = next          # 다음 노드로 이동

 

이 루프가 끝나면:

• curr은 None (즉, 리스트 끝을 넘은 상태)
• prev는 뒤집힌 리스트의 시작 지점, 즉 새로운 head!

---

🔍 예를 들어서:

리스트가 1 → 2 → 3 → 4였다면,
루프가 끝난 후:

• prev: 4 → 3 → 2 → 1
• curr: None

---

✅ 요약:

변수	의미
curr	루프가 끝나면 None (끝났다는 뜻)
prev	뒤집어진 리스트의 head

그래서 뒤집힌 리스트를 쓰고 싶을 땐 prev를 사용해야 해요!

reversed_head = prev

 

문제 풀이

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        # 두 포인터 초기화: slow는 한 칸씩, fast는 두 칸씩 이동
        slow = fast = head
        prev = None  # reverse된 리스트의 시작을 가리킬 포인터

        # 연결 리스트의 절반을 순회하면서 동시에 reverse 수행
        while fast and fast.next:
            fast = fast.next.next  # fast는 두 칸 이동 (끝에 먼저 도달)

            nxt = slow.next        # 현재 slow의 다음 노드를 임시 저장 (잃어버리지 않기 위해)
            slow.next = prev       # 현재 노드의 방향을 뒤집음 (역방향으로 연결)
            prev = slow            # prev는 현재 노드가 됨 (한 칸 뒤로 이동)
            slow = nxt             # slow는 다음 노드로 한 칸 이동

        """
        while 루프 종료 시점:
        - fast가 끝에 도달하면 slow는 정확히 리스트의 절반 위치
        - slow는 중간 이후, 즉 리스트의 오른쪽 절반(정방향)의 시작 노드를 가리킴
        - prev는 왼쪽 절반을 역방향으로 뒤집은 리스트의 시작을 가리킴, 
        		 즉, 리스트의 왼쪽 절반(reverse된 것)이 뒤집힌 상태
        """
        
        twin_sum_max = 0  # twin sum의 최대값을 저장할 변수

        # 오른쪽 절반(slow)과 뒤집힌 왼쪽 절반(prev)을 동시에 순회하며 twin sum 계산
        while slow:
            twin_sum = slow.val + prev.val  # 현재 위치의 twin sum 계산
            twin_sum_max = max(twin_sum_max, twin_sum)  # 최대값으로 갱신
            slow = slow.next   # 오른쪽 절반 다음 노드로 이동
            prev = prev.next   # 왼쪽 절반(역방향) 다음 노드로 이동

        # 최대 twin sum 반환
        return twin_sum_max