[코딩 인터뷰]자료구조 - 연결리스트 문제(Python)

 

[ 연결리스트]

 Python으로 노드와 연결리스트를 간단하게 구현했습니다.

# 노드
class Node:
    def __init__(self, d):
        self.data = d
        self.next = None
# 연결리스트        
class LinkedList:
    def __init__(self, data):
        self.head = Node(data)

    def appendNode(self, data):
        now = self.head
        while now.next is not None:
            now = now.next
        now.next = Node(data)
        
    def appendNode2(self, node:Node):
        now = self.head
        while now.next is not None:
            now = now.next
        now.next = node

    def print_all(self):
        now = self.head
        nodes = []
        while now is not None:
            nodes.append(now.data)
            now = now.next
        print(*nodes, sep=' → ')

 

 

[ 중복 없애기 ]

 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 알고리즘

예시) A→B→C→B→A→C→D ⇒ A→B→C→D

def deleteDups(n: Node):
    datas = set()
    pre = Node()
    while n != None:
        if n.data in datas:
            pre.next = n.next
        else:
            datas.add(n.data)
            pre = n
        n = n.next
        
def deleteDups_LinkdedList(n: LinkedList):
    deleteDups(n.head)

👀 연결리스트의 head, 즉 Node를 매개변수로 작동하는 코드입니다. 연결리스트를 매개변수로 할 경우 n.head가 n이 되도록 코드를 수정하면 됩니다.

 

 

[ 뒤에서 k번째 원소 구하기 ]

 단방향 연결리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘

예시) A→B→C→B→A→C→D, 0 ⇒ D

def kthToLast(n: LinkedList, k: int):
    p1 = n.head
    p2 = n.head
    if p1 is None: return None
    for i in range(k+1):
        p1 = p1.next
    while p1 != None:
        p1 = p1.next
        p2 = p2.next
    return p2

👀 Runner 기법으로 풀었습니다. 2개의 변수(p1과 p2)를 사용하여 p1를 k만큼 노드를 이동시킨 후 p1이 마지막이 될 때까지 p1과 p2를 함께 이동했습니다.

 

 

[ 중간 노드 삭제 ]

 단반향 연결리스트가 주어졌을 때 중간(처음과 끝이 아닌 것)에 있는 노드 하나를 삭제하는 알고리즘

def deleteNode(n: LinkedList):
    now = n.head
    if now is None or now.next is None or now.next.next is None:
        return False
    next = now.next.next
    now.next = next
    return True

👀 문제의 설명이 정확하지 않아서 노드가 [처음-끝]이 아닌 경우 2번째 노드를 삭제하는 알고리즘으로 작성했습니다.

 

 

[ 분할 ]

 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 알고리즘

예시) 3→5→8→5→10→2→1, 5 ⇒ 3→1→2→10→5→5→8

def partition(n: Node, x: int):
    now = n
    lS, lE, rS, rE = None, None, None, None

    while now is not None:
        next = now.next
        now.next = None
        if now.data < x:
            if lS is None: lS = now
            else: lE.next = now
            lE = now
        else:
            if rS is None: rS = now
            else: rE.next = now
            rE = now
        now = next
        
    if lS is None: return rS
    lE.next = rS
    return lS

👀 변수를 왼쪽과 오른쪽을 각각 시작과 끝으로 나누어서 값을 연결한 뒤 왼쪽 끝과 오른쪽 시작을 합쳤습니다.

def partition_LinkedList(n: LinkedList, x:int):
    now = n.head
    left, right = None, None
    lE = None
    while now is not None:
        next = now.next
        if now.data < x:
            if lE:
                if left is None:
                    left = LinkedList(lE.data)
                else:
                    left.appendNode(lE.data)
            lE = now
        else:
            if right is None:
                right = LinkedList(now.data)
            else:
                right.appendNode(now.data)
        now = next
    if right:
        lE.next = right.head
    left.appendNode2(lE)
    return left

👀 연결리스트에 print_all이란 함수를 사용하기 위해서 연결리스트로 변경하여 풀어보았습니다.

 

 

[ 리스트의 합 ]

 역순으로 한 자리씩 숫자 표현되어있는 연결리스트 두 개가 있을 때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 알고리즘

예시) 7→1→6 + 5→9→2 ⇒ 2→1→9

def addLists(l1:LinkedList, l2:LinkedList):
    l1, l2 = l1.head, l2.head
    l1_v, l2_v = l1.data, l2.data
    r = None
    carry = 0
    while l1 is not None or l2 is not None:
        a, b = divmod(l1_v + l2_v + carry, 10)
        carry = a

        if r is None:
            r = LinkedList(b)
        else:
            r.appendNode(b)

        try:
            l1 = l1.next
            l1_v = l1.data
        except:
            l1_v = 0

        try:
            l2 = l2.next
            l2_v = l2.data
        except:
            l2_v = 0
    if carry:
        r.appendNode(a)
    return r

👀 자릿수가 다를 경우 오류가 생겨서 try except로 해결했습니다.

 

 

[ 회문 ]

 주어진 연결리스트가 회문인지 검사하는 알고리즘

예시) 0→1→2→1→0 ⇒ True

def reverse(node: Node):
    head = None
    while node is not None:
        n = Node(node.data)
        n.next = head
        head = n
        node = node.next
    return head

def isPalindrome(n):
    n_r = reverse(n)
    while n is not None and n_r is not None:
        if n.data != n_r.data:
            return False
        n = n.next
        n_r = n_r.next
    return n is None and n_r is None

👀 주어진 연결리스트를 뒤집은 연결리스트를 생성 후 비교하였습니다.

 

 

[ 교집합 ]

 단방향 연결리스트 두 개가 주어졌을 때 이 두 리스트의 교집합 노드를 찾은 뒤 반환하는 코드를 작성하라.

⭐ 교집합 : 노드의 값이 아니라 노드의 주소가 완전히 같은 경우입니다. 즉, 첫 번째 리스트에 있는 k번째 노드와 두 번째 리스트에 있는 j번째 노드가 주소까지 완전히 같다면 이 노드는 교집합의 원소입니다.

예시) 교집합 부분은 7→2→1

# 연결리스트 끝과 사이즈 계산
def getTailAndSize(l: LinkedList):
    if l.head is None: return None
    size = 1
    now = l.head
    while now.next is not None:
        size += 1
        now = now.next
    return (now, size)

def findIntersection(l1: LinkedList, l2: LinkedList):
    if l1 is None or l2 is None: return None

    # 연결리스트 끝과 사이즈 구하기
    l1_tail, l1_size = getTailAndSize(l1)
    l2_tail, l2_size = getTailAndSize(l2)

    if l1_tail is not l2_tail: return None

    # 연결리스트 길이 판별
    l_long = l1.head if l1_size > l2_size else l2.head
    l_short = l2.head if l_long is l_long else l1.head

    # 연결리스트 중 긴 부분 짧은 부분 차이만큼 이동
    for i in range(max(l1_size, l2_size) - min(l1_size, l2_size)):
        l_long = l_long.next

    while l_long != l_short:
        l_short = l_short.next
        l_long = l_long.next

    return l_long

👀 맨 끝의 노드가 같은지 우선 확인합니다. 맨 끝의 노드가 같다면 교집합이 존재한다는 의미로 두 개의 리스트 중 짧은 리스트를 기준으로 비교하기 위하여 길이를 알아냅니다. 그 뒤에 긴 쪽을 짧은 부분만큼 이동시킨 후 비교합니다.

 

 

[ 루프 발견 ]

 순환 연결리스트가 주어졌을 때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘

⭐ 순환 연결리스트 : 노드의 next 포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서는 변질된 방식의 연결리스트

예시) 첫째 노드 : B

def findCircularBeginning(n: Node):
    nodes = set()
    now = n
    while now not in nodes:
        nodes.add(now)
        # 순환이 되지 않을 경우
        if now.next is None: return None
        now = n.next
    return now

👀 set()을 준비하여 주소 값이 존재하면 그 부분을 순환되는 부분의 첫 번째 노드라고 생각했습니다. 책에서는 Runner 기법을 사용하였습니다.