연결 리스트는 컴퓨터과학에서 배열과 함께 가장 기본이 되는 대표적인 선형 자료구조 중 하나로 다양한 추상 자료형 구현의 기반이 된다.

동적으로 새로운 노드를 삽입하거나 삭제하기가 간편하며, 연결 구조를 통해 메모리를 연속적으로 사용하지 않아도 되기 때문에 관리도 쉽다. 또한 데이터를 구조체로 묶어서 포인터로 연결한다는 개념은 여러 가지 방법으로 다양하게 활용이 가능하다.

연결 리스트는 배열과는 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수 시간에 접근할 수 없다. 즉 탐색에는 O(n)이 소요된다. 반면, 시작 또는 끝 지점에 아이템을 추가하거나 삭제, 추출하는 작업은 O(1)에 가능하다.

이제 연결 리스트를 이용한 다양한 문제를 직접 풀이해 보면서 연결 리스트의 특징과 활용 방법을 하나씩 살펴보자.

문제1

두 수의 덧셈 - 역순으로 저장된 연결 리스트의 숫자를 더하라.

• 입력
  (2->4->3) + (5->6->4)
• 출력
  7->0->8
• 설명
  342 + 465 = 807

풀이1_자료형 변환

얼핏 드는 생각은, 연결 리스트를 문자열로 이어 붙인 다음에 숫자로 변환하고, 이를 모두 계산한 후 다시 연결 리스트로 바꾸면 쉽게 풀이할 수 있을 것 같다. 역순으로 뒤집어야해서 수행 시간이 제법 소요될 것으로 예상되지만 풀이는 쉬울 것 같으므로 시도해보자. 먼저, 역순으로 된 연결 리스트를 뒤집어야 한다.

def reverse_list(head:Listnode):
    node, prev = head, None
    
    while node:
        next, node.next = node.next, prev
        prev, node = node, next

    return prev

다음 노드의 next와 현재 노드 node를 파라미터로 지정한 함수를 계속해서 재귀 호출한다. node.next 에는 이전 prev 리스트를 계속 연결해주면서 node가 None이 될 때까지 재귀 호출하면 마지막에는 백트래킹되면서 연결 리스트가 거꾸로 연결된다. 여기서 맨 처음에 리턴된 prev는 뒤집힌 연결리스트의 첫 번째 노드가 된다.

이번에는 덧셈 연산을 위해 연결 리스트를 파이썬의 리스트로 변경해야 한다. 이 역할을 하는 함수를 작성해보자. 아래 코드는 node를 반복하며 값을 리스트에 추가한다.

def to_list(node:Listnode):
    list = []
    while node:
        list.append(node.val)
        node = node.next
    return list

먼저 연결 리스트를 뒤집었고 이를 파이썬 리스트로 변환했다. 변환한 리스트를 각각 a,b라고 했을 때

result = int(''.join(str(e) for e in a)) +
	int(''.join(str(e) for e in b))

이와 같이 해결할 수 있다. str(e)로 각 항목을 문자로 변경한 다음 join()으로 합쳤다. 그런데 덧셈 연산을 위해서는 다시 숫자형이 되어야 한다. 따라서 최종값은 다시 int로 변경해줘야 한다.

마지막 결과를 연결리스트로 return해야 하기 때문에 리스트를 연결리스트로 변경하는 함수도 작성해보자.

def to_reversed_linkedlist(result:Listnode):
    prev = None
    for r in result:
        node = Listnode(r)
        node.next = prev
        prev = node

    return node

이 코드는 순서대로 엮어 나가는 방식으로 구현했는데, 이렇게 하면 뒤집힌 연결 리스트가 된다.

따라서 마지막으로 to_reversed_linkedlist()를 사용하여 최종 계산 결과를 연결리스트로 변환하는 작업을 하면 된다. 이제 모두 통합하면 전체 코드는 아래와 같다.

class Solution(object):
    
    def reverse_list(self,head):
        node, prev = head, None
        while node:
            next, node.next = node.next, prev
            prev, node = node, next
        return prev
    
    
    def to_list(self,node):
        list = []
        while node:
            list.append(node.val)
            node = node.next
        return list
    
    
    def to_reversed_linked_list(self,result):
        prev = None
        for r in result:
            node = ListNode(r)
            node.next = prev
            prev = node
        return node
    
    
    def addTwoNumbers(self, l1, l2):
        a = self.to_list(self.reverse_list(l1))
        b = self.to_list(self.reverse_list(l2))
        
        result = int(''.join(str(e) for e in a)) + int(''.join(str(e) for e in b))
        return self.to_reversed_linked_list(str(result))

코드가 다소 길지만 풀이 자체는 전혀 어렵지 않다. 수행속도에도 크게 문제가 없다. 하지만 이 같은 방식이 깔끔한 풀이라고 할 수도 없다. 좀 더 깔끔한 방식으로 풀이할 수 있는 방법을 찾아보자.

풀이2_전가산기

sum = 0
if l1:
    sum += l1.val
    l1 = l1.next
if l2:
    sum += l2.val
    l2 = l2.next

이 코드를 통해서 먼저 두 입력값의 합을 구한다. 두 입력값의 연산을 수행하고 다음과 같이 자릿수가 넘어갈 경우에는 자리올림수를 설정할 것이다.

carry, val = divmod(sum + carry, 10)

이처럼 자리 올림수를 계산하게 되는데, 전가산기와 마찬가지로 이전의 자리 올림수 carry를 받아오고, 이를 divmod()로 계산한다.

carry, val = divmod(sum + carry, 10)을 하게 되면, 가산 결과가 두 자릿수가 될 경우 몫은 자리올림수로 설정해 다음번 연산에 사용하게 되고 나머지는 값으로 취하게 된다. 이제 이 값을 연결 리스트로 만들어 주면 된다. 원래 가산기는 논리 회로를 이용해 이진 연산을 수행하지만 여기서는 전체적인 구조만 참고하여 십진 연산에 응용해보았다. 전체 코드는 다음과 같다.

    def addTwoNumbers(self, l1, l2):
        root = head = ListNode(0)
        carry = 0

        while l1 or l2 or carry:
            sum = 0
            if l1:
                sum += l1.val
                l1 = l1.next
            if l2:
                sum += l2.val
                l2 = l2.next
                
            carry, val = divmod(sum+carry, 10)
            head.next = ListNode(val)
            head = head.next
            
        return root.next

문제2

연결 리스트를 입력받아 페어(pair) 단위로 스왑하라.

• 입력
  1->2->3->4
• 출력
  2->1->4->3

풀이1_값만 교환

매우 직관적인 방법으로 풀이해보자. 연결 리스트의 노드를 변경하는 게 아닌, 노드 구조는 그대로 유지하되 값만 변경하는 방법이다. 사실 이 방식은 실용성과는 다소 거리가 있다. 대개 연결 리스트는 복잡한 여러 가지 값들의 구조체로 구성되어 있고, 사실상 값만 바꾸는 것은 매우 어려운 일이기 때문이다. 그러나 이 문제에서는 단 하나의 값으로 구성된 단순한 연결 리스트이고, 값을 바꾸는 정도는 어렵지 않게 가능하다.

    def swapPairs(self, head):
        cur = head
        
        while cur and cur.next:
            cur.val, cur.next.val = cur.next.val, cur.val
            cur = cur.next.next
                      
        return head

위와 같은 방법은 변칙적이므로 만약 코딩 테스트 이후 코드 리뷰를 진행하다가 좋지 않은 피드백을 받을 가능성도 있다. 좋지 않은 피드백을 받게 된다면, 빨리 풀기 위해 시도한 방법이라는 사실을 충부히 어필하고 다른 풀이법에 대해 설명할 수 있어야 한다.

풀이2_반복 구조로 스왑

단순히 값을 바꾸는 일에 비해 연결 리스트 자체를 바꾸는 일은 생각보다 다소 복잡한 문제다. 왜냐하면 1->2->3->4->5->6 인 연결 리스트가 있을 경우, 3->4 를 4->3으로 바꾼다고 할 때 단순히 둘만 바꾼다고 끝나는 문제가 아니라, 그 앞인 2가 가리키는 연결 리스트와 5로 연결되는 연결 리스트도 다 같이 변경해야 하기 때문이다.

b = a.next
a.next = b.next
b.next = a

이처럼 b가 a를 가리키고 a는 b의 다음을 가리키도록 변경한다. 그러나 아직 a의 이전 노드가 b를 가리키지는 못한다.

prev.next = b
a = a.next
prev = prev.next.next

a의 이전 노드 prev가 b를 가리키게 하고, 다음번 비교를 위해 prev는 두 칸 앞으로 이동한다. 그리고 다시 다음번 교환을 진행할 것이다. 변수명을 문제 풀이에 맞게 조금 수정하고 while문을 포함한 전체 코드로 정리해보면 다음과 같다.

    def swapPairs(self, head):
        root = prev = ListNode(None)
        prev.next = head
        
        while head and head.next:
            b = head.next
            head.next = b.next
            b.next = head
            
            prev.next = b
            
            head = head.next
            prev = prev.next.next
            
        return root.next

이전 풀이들과 달리 연결 리스트의 head를 가리키는 노드가 직접 바뀌는 풀이이므로 head를 리턴하지 못하고 그 이전 값을 root로 별도로 설정한 다음 root.next를 리턴하게 했다.

문제3

홀짝 연결리스트_연결 리스트를 홀수 노드 다음에 짝수 노드가 오도록 재구성하라. 공간 복잡도 O(1), 시간 복잡도 O(n)에 풀이하라.

• 입력
  1->2->3->4->5->NULL
  2->1->3->5->6->4->7->NULL
• 출력
  1->3->5->2->4->NULL
  2->3->6->7->1->5->4->NULL

홀수 노드 다음에 짝수 노드가 오게 재구성하라고 했으니 홀(odd), 짝(even) 각 노드를 구성한 다음 홀수 노드의 마지막을 짝수 노드의 처음과 이어주면 될 것 같다.

먼저, 입력값은 1->2->3->4->5 로 구성된 연결 리스트로 가정해보자.

odd = head
even = head.next
even_head = head.next

홀수 변수는 head이고, 짝수 변수는 head.next이다. 짝수의 헤드는 head.next이므로, even_head = even = head.next 로 일단 시작한다.

while even and even.next:
    odd.next, even.next = odd.next.next, even.next.next
    odd, even = odd.next, even.next

이와 같이 while 반복문으로 루프를 돌면서 처리한다.

전체 코드는 다음과 같다.

    def oddEvenList(self, head):
            if head is None:
                return None

            odd = head
            even = head.next
            even_head = head.next

            while even and even.next:
                odd.next, even.next = odd.next.next, even.next.next
                odd, even = odd.next, even.next

            odd.next = even_head
            return head