연결 리스트 with LeetCode 234

1. 들어가며

참고: 책 <<파이썬 알고리즘 인터뷰>> pp.199-210

연결 리스트에 대해 다시 공부했다.
처음 연결 리스트를 접했을 때는 잘 이해가 되지 않았었다. 참고한 책에서는 연결 리스트를 클래스로 구현하여 관련 문제를 풀이했는데, 당시 내가 '참조'에 익숙하지 않아 연결 리스트의 구조를 직관적으로 받아들이지 못했기 때문이다.

보통 알고리즘 문제를 풀 때 클래스 구현을 잘 안 하는데, LeetCode의 자료구조 문제는 클래스를 활용하여 풀도록 문제가 구성되어 있어서 자료구조 이해에 크게 도움이 되는 것 같다. 자료구조 문제는 LeetCode에서 풀어보는 것을 추천한다!

---

2. 연결 리스트(Linked List)

• 연결 리스트란?

  • 배열(array)과 함께 가장 기본이 되는 선형 자료구조 중 하나
  • 배열과는 달리 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리가 쉽다.
    이미지 출처: wikipedia 'linked list' 캡처

• 시간 복잡도

  • 상수 시간에 조회가 가능한 배열과는 달리 특정 인덱스에 접근하는 데 O(n)의 시간이 소요된다. 그 이유는 연결 리스트의 첫 번째 노드(head)에서 시작하여 원하는 인덱스까지 하나하나 읽어나가야 하기 때문이다.
  • 시작 지점 또는 끝 지점에 노드를 추가하는 작업은 O(1)에 가능하다.

• 런너(Runner) 기법
  

  • 런너 기법은 연결 리스트 순회 시 fast와 slow 두 개의 포인터를 사용한다.
  • fast 포인터는 slow 포인터보다 한 번에 많은 칸을 움직인다. 만약 fast가 slow보다 2배 많이 움직인다면, fast가 연결 리스트 끝 지점에 도달했을 때 slow는 중간 지점에 위치한다. 이와 같은 방식으로 두 포인터를 활용하여 연결 리스트 뒤집기, 팰린드롬 체크 등에 유용하게 쓰이는 기법이 런너 기법이다.

---

3. 문제 풀이: LeetCode 234

문제: LeetCode 234

easy 난이도의 문제지만, 연결 리스트 클래스를 파이썬 리스트로 바꾸지 않고 그대로 사용하여 풀어보는 게 처음이라면 결코 쉬운 문제는 아니라고 생각한다.

문제 해결을 위해 3가지를 이해해야 한다.

1) 연결 리스트 클래스

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

인스턴스 변수 val은 해당 노드의 값이다.
인스턴스 변수 next는 다음 노드를 참조한다.

2) 노드 개수(홀수? or 짝수?)

노드 개수가 홀수일 경우 fast가 끝에 도달했을 때 slow는 연결 리스트의 중앙 노드를 가리킨다. 팰린드롬 여부를 검사하는 것이 목표이기에 이때 slow를 한 번 더 이동시켜주는 작업이 필요하다.

3) 다중 할당

아래 두 코드의 차이를 이해해야 한다.

# slow: 2->3
# rev: 1

# 1
slow, rev, rev.next = slow.next, slow, rev
'''
slow: 3
rev: 2->1
'''

# 2
rev, rev.next = slow, rev
slow = slow.next
'''
slow: 1
rev: 2->1
'''

1번과 2번 코드는 결과가 다르다. 2번의 경우 첫 번째 코드에서 rev와 slow가 같은 노드를 참조하도록 되어 있기 때문에 두 번째 코드가 실행되면 slow는 3이 아닌 rev.next가 가리키는 1이 된다.

아래는 전체 코드이다.

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

class Solution(object):
    def isPalindrome(self, head):
        fast = head
        slow = head
        rev = ListNode()

        while fast and fast.next:
            fast = fast.next.next
            slow, rev, rev.next = slow.next, slow, rev
        
        # 노드 개수가 홀수일 경우
        if fast:
            slow = slow.next
        
        while slow:
            if slow.val != rev.val:
                break
            slow, rev = slow.next, rev.next
        else:
            return True
        return False