[LeetCode] 876번: 연결 리스트

Goal

1. 연결 리스트 이해하기
2. 가장 간단한 연결 리스트 알고리즘 문제 풀어보기

 

연결 리스트(Linked List)란?

연결 리스트란 리스트 안에 있는 항목들이 그 다음 순서로 오는 항목과 연결되어 정해진 순서로 묶여 있는 리스트 구조를 말한다.

연결 리스트 (Linked List)

 

LeetCode 876번: Middle of the Linked List (풀어보기)

Hint

1. head라는 연결 리스트 구조의 정의 :
      head.val = 현재 위치의 수
      head.next= 다음 연결된 리스트
2. 총 개수가 1개일 때는 현재 위치와 중간 지점의 위치가 같다
3. 연결된 리스트의 개수가 하나씩 늘어날 때마다 현재 위치와 중간 지점의 위치가 어떻게 변하는지 생각해보자
4. 총 개수가 홀수일 때와 짝수일 때 현재 위치와 중간 지점의 위치가 어떻게 옮겨지는지 생각해보자
5. 짝수일 때는 포인터가 같이 한칸씩 움직이고, 홀수일 때는 현재 포인터 위치만 한칸 움직인다

두개의 포인터의 위치가 어떻게 바뀌는지 확인

 

Solution

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        even = False			# 현재 총 개수가 짝수인지 확인
        now = middle = head		# 현재 위치를 알려주는 포인터와 중간 지점을 알려주는 포인터를 정의
        
        # 그 다음 순서로 오는 리스트가 있는 동안에 반복되는 코드
        while now.next:
            even = not even	# 짝수였으면 그 다음은 홀수, 홀수였으면 그 다음은 짝수가 된다
            now = now.next	# 현재 위치를 그 다음 리스트로 포인터를 옮겨준다
            
            # 총 개수가 짝수라면 중간 지점 포인터를 한칸 옮겨준다
            if even:	
                middle = middle.next
        
        # 중간 지점 포인터가 가르키는 리스트를 반환한다
        return middle