파이썬 알고리즘 - 선택 노드를 기준으로 링크드리스트(LinkedList) 분할

개발자 면접 트레이딩 - 파이썬 알고리즘 문제(8)

 

 

(1). 개발자 면접 트레이닝 - 특정 노드를 입력 받아 링크드리스트 분할 후 병합

① 링크드리스트는 다음 노드의 위치를 가르키고 있는 포인트 보유

② 분할(Split) 후 다시 병합(Merge)하는 것이 중요

③ 첫 번째 노드(Node)의 위치를 지정하는 것이 중요

④ 예를들어 [6, 3, 8, 1, 5, 9]  에서 5 노드 기준으로 나누면 -> [3, 1, 5, 6, 8, 9]  출력

 

 

(2). 소스 코드

PYTHON

#split_merge_linkedlist.py
import unittest

class Node:
    def __init__(self, item):
        self.val = item
        self.next = None

class LinkedList:
    def __init__(self, item):
        self.head = Node(item)

    def add(self, item):
        cur = self.head
        while cur.next is not None:
            cur = cur.next
        cur.next = Node(item)

    def getHead(self):
        return self.head

    def printlist(self):
        cur = self.head
        res = []
        while cur is not None:
            res.append(cur.val)
            cur = cur.next
        return str(res)

def solution(ll, key):
    cur = ll.getHead()
    pre = None
    post = None
    while cur is not None:
        if cur.val != key:
            if cur.val > key:
                if post is None:
                    post = LinkedList(cur.val)
                else:
                    post.add(cur.val)
            elif cur.val < key:
                if pre is None:
                    pre = LinkedList(cur.val)
                else:
                    pre.add(cur.val)
        cur = cur.next

    cur = pre.getHead()
    while cur.next is not None:
        cur = cur.next
    cur.next = Node(key)
    cur.next.next = post.getHead()
    return pre.printlist()

class LinkedListTest(unittest.TestCase):
    def test(self):
        ll = LinkedList(6)
        ll.add(3)
        ll.add(8)
        ll.add(1)
        ll.add(5)
        ll.add(9)
        self.assertEqual("[3, 1, 5, 6, 8, 10]", solution(ll,5))
        print(solution(ll,5))

unittest.main()

 

(3). 소스 코드 분석

① 14 라인 : 헤드(Head) 노드 선언

② 24 라인 : 현재 링크드리스트(LinkedList)의 헤드 반환 함수 선언

③ 36 라인 : 분할 및 병합 위한 Soluteion 메소드 선언

④ 42 라인 : key(분할 기준) 노드를 입력받아 분할 작업 구간

⑤ 59 라인 : 분할된 링크드리스트(LinkedList)를 다시 병합 작업 구간

⑥ 68 ~ 끝 : 링크드리스트(LinkedList) 선언 및 assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

LinkedList(링크드리스트) 관련 알고리즘 문제는 자주 활용, 출제 되므로 Java, C  등으로 작성해보자.

 

참고로 이 예제를 여러 가지 방법으로 해결해보자. 이 포스팅 보다 더 좋은 방법으로!

(4). 실행결과1 - 단위테스트 정상 출력(병합 결과 같을 경우)

 

 

(5). 실행결과2 - 단위테스트 정상 출력(병합 다를 경우)