파이썬 알고리즘 - 링크드리스트(LinkedList)에서 끝 에서 N 번째 값

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

 

 

(1). 개발자 면접 트레이닝 - 링크드리스트에서 끝에서 지정 하는 노드의 값 구하는 알고리즘

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

② 파이썬 클래스 Next 변수 활용

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

④ 예를들어 [3, 4, 5, 6, 7, 7, 8, 9, 9]  에서 끝에서 2번째의 노드의 값은 은 -> 9 출력

 

 

(2). 소스 코드

PYTHON

#last_n_val_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 printlist(self):
        cur = self.head
        res = []
        while cur is not None:
            res.append(cur.val)
            cur = cur.next
        return str(res)

    #마지막에서 N 번째 노드 값 출력
    def kth_element_from_last(self,k):
        p1 = self.head
        p2 = self.head
        if k != 0:
            for i in range(k):
                p2 = p2.next
            if p2 is None:
                return None
        while p2.next is not None:
            p2 = p2.next
            p1 = p1.next
        return p1.val

class LinkedListTest(unittest.TestCase):
    def test(self):
        ll = LinkedList(3)
        ll.add(4)
        ll.add(5)
        ll.add(6)
        ll.add(4)
        ll.add(7)
        ll.add(4)
        self.assertEqual(4, ll.kth_element_from_last(0))
        self.assertEqual(7, ll.kth_element_from_last(1))
        self.assertEqual(4, ll.kth_element_from_last(2))
        self.assertEqual(6, ll.kth_element_from_last(3))
        self.assertEqual(5, ll.kth_element_from_last(4))
        self.assertEqual(4, ll.kth_element_from_last(5))
        self.assertEqual(3, ll.kth_element_from_last(6))
        self.assertEqual(None, ll.kth_element_from_last(7))

unittest.main()

 

(3). 소스 코드 분석

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

② 20 라인 : 다음 노드의 주소(Next)가 None이 아닐 경우 다음 노드 연결

③ 37 라인 : 시작 지점을 다르게 하기 위해 P1, P2 두 개의 노드 선언

④ 49 라인 : 지정 위치의 노드 값 출력

⑤ 60 ~ 끝 : assertEqula 단위 테스트 함수를 사용하여 입력 결과와 출력결과를 비교

 

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

 

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

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

 

 

(5). 실행결과2 - 단위테스트 에러 출력(비교 다를 경우)