연결리스트 문제풀이

📌코딩인터뷰 완전분석 - 면접문제 - 연결리스트part 문제풀이 (파이썬 사용)

2.1 중복 없애기: 정렬되어 있지 않은 연결리스트가 주어졌을 때 이 리스트에서 중복되는 원소를 제거하는 코드를 작성하라.

def remove_duplication(node):         #중복 제거하는 함수 remove_duplication(node)
    forcompare = {}                   #구분을 위한 forcompare 딕셔너리 만들기
    previous = None                   #previous 변수에 none값 넣어주기

    while node:                       #node가 존재하는한 while문 돌기
        if node.data in forcompare:   #node의 데이터가 forcompare 딕셔너리 안에 있다면 중복이 존재하는것이기 때문에
            previous.next = node.next #node의 next 데이터를 node 자리(previous.next)에 오도록 해준다.
        else:                         #if의 경우가 아니라면
            forcompare[node.data] = 1 #forcompare 딕셔너리 안에 node의 데이터를 키 값으로 하고 value가 1이 되도록 삽입하여준다.

        previous = node               #node의 값을 previous에 넣어주고
        node = node.next              #node.next의 값을 node에 넣어준다. 이렇게 함으로써 리스트를 처음부터 끝까지 돌게된다.

2.2 뒤에서 k번째 원소 구하기: 단방향 연결리스트가 주어졌을 때 뒤에서 k번째 원소를 찾는 알고리즘을 구현하라.

📍 재귀적 방법

#재귀적 방법
def recursive(k, node):
    #마지막 원소를 만나면, 0으로 설정된 카운터 값을 반화하도록 한다.
    if not node:
        return[0,None]

    # 재귀적 방법을 이용하여 연결리스트의 끝으로 이동한다.
    for_count = recursive(k, node.next)

    # 뒤에서 몇번째인지 카운트한다.
    for_count[0] += 1

    # 찾고자 하는 k번째 라면 데이터의 값을 할당하고 리턴한다.
    if for_count[0] == k:
        for_count[1] == node.data
        return for_count

    # 찾고자 하는 원소가 아니라면 카운트만 반영한 뒤 리턴한다.
    else:
        return for_count

📍 순환적 방법

# 순환적 방법
# 두개의 포인터(p1, p2)를 두고 그 중 한개의 포인터(p1)를 미리 k만큼 이동시켜 둔다
# 이동시킨 포인터(p1)가 연결리스트의 끝에 도착했을 때 나머지 포인터(p2)가 끝에서 k번째 위치에 도달하게 된다.

def iterative(k, head):
    find_end = head #미리 k만큼 이동시켜 놓는 p1 포인터
    find_k = head   #p2 포인터

    # 한개의 포인터를 미리 k만큼 이동
    for _ in range(k):
        if not find_end:
            return None
        find_end = find_end.next

    # 미리 k만큼 이동한 포인터가 리스트의 끝에 도달할때 까지 두개의 포인터 모두 한칸씩 이동
    while find_end.next:
        find_k = find_k.next
        find_end = find_end.next

    # 끝에서 k번째에 있는 데이터 리턴
    return find_k.data

2.3 중간 노드 삭제: 단방향 연결리스트가 주어졌을 때 중간(정확히 가운데 노드일 필요는 없고 처음과 끝 노드만 아니면 된다)에 있는 노드 하나를 삭제하는 알고리즘을 구현하라. 단, 삭제할 노드에만 접근할 수 있다.

#단방향 연결리스트이기 때문에 삭제할 노드에만 접근할 수 있다. 
#그러므로 이 문제에 대한 해법은 다음 노드의 데이터를 현재 노드에 복사한 다음에,
#다음 노드를 지우는 것이다.

def deleteNode(node):
    if not node or not node.next:
        return False
    next = node.next # 노드의 다음 노드를 next변수에 넣어준다.
    node.data = next.data # 다음 노드의 data를 현재 노드의 data에 넣어준다.
    node.next = next.next # 다음 다음 노드를 다음 노드에 넣어줌으로서 다음 노드를 지운다.
    return True

2.4 분할: 값 x가 주어졌을 때 x보다 작은 노드들을 x보다 크거나 같은 노드들보다 앞에 오도록 하는 코드를 작성하라. 만약 x가 리스트에 있다면 x는 그보다 작은 원소들보다 뒤에 나오기만 하면 된다. 즉, 원소x는 '오른쪽 그룹'어딘가에만 존재하면 된다. 왼쪽과 오른쪽 그룹 사이에 있을 필요는 없다.

#풀이 방법: 서로 다른 연결리스트 두개를 만들어서 하나에는 x보다 작은 원소들을 보관하고, 
#다른 하나에는 x보다 큰 원소들을 보관한다.
#입력으로 주어진 연결리스트를 순회하면서, before 리스트 아니면 after 리스트에 원소를 삽입한다. 
#연결리스트의 마지막에 도달하면 분할 작업이 끝난 것이므로, before와 after를 합치면 된다.

def partition(node, x):
    smallerstart = None
    smallerend = None
    biggerstart = None
    biggerend = None

    while(node != None):              # 리스트가 비어있지 않다면 반복한다.
        next = node.next
        node.next = None
        if(node.data < x):            # 노드의 데이터가 x보다 작을경우
            if(smallerstart == None): # smaller 리스트가 비어있을경우
                smallerstart = node
                smallerend = smallerstart;
            else:                     # smaller 리스트가 비어있는게 아닐 경우
                smallerend.next = node
                smallerend = node
        else:                         # 노드의 데이터가 x보다 클경우
            if(biggerstart == None):  # bigger 리스트가 비어있을경우
                biggerstart = node
                biggerend = biggerstart
            else:                     # bigger 리스트가 비어있는게 아닐 경우
                biggerend.next = node
                biggerend = node
        node = next                   # 노드를 다음노드로 가도록 한다.

    if(smallerstart == None):         # smaller 리스트가 비어있을경우에는 bigger 리스트만 리턴한다.
        return biggerstart
    
    smallerend.next = biggerstart     # smaller 리스트의 뒤에 bigger 리스트를 붙여주고 smaller 리스트를 리턴한다.
    return smallerstart

2.5 리스트의 합: 연결리스트로 숫자를 표현할 때 각 노드가 자릿수 하나를 가리키는 방식으로 표현할 수 있다. 각 숫자는 역순으로 배열되어 있는데, 죽, 첫번째 자릿수가 리스트의 맨 앞에 위치하도록 배열된다는 뜻이다. 이와 같은 방식으로 표현된 숫자 두 개가 있을때, 이 두 수를 더하여 그 합을 연결리스트로 반환하는 함수를 작성하라.

#풀이 방법: 자릿수 대로 더해주고 올림이 발생하면 carry해 주면서 리스트가 끝날때까지 더해준다.

def addlists(list1, list2, carry):
    if(list1 == None and list2 == None and carry == 0):
        return None
    
    result = None
    value = carry
    if(list1 != None):
        value += list1.data
    if(list2 != None):
        value += list2.data

    result.data = value % 10

    #재귀
    if(list1 != None or list2 != None):
        more = addlists(None if list1 == None else list1.next, None if list2 == None else list2.next, 1 if value >= 10 else 0)

        result.next = more

    return result

😭 풀어보긴 했는데 이게 맞는지는 모르겠습니다,,,