[Python] 단일 연결 리스트 / 끝에서 k번째 찾기 / 연결 리스트 분할

연결 리스트의 끝에서 k번째 노드 찾기

이전 게시물에서 작성했던 FIFO구조 연결리스트를 이용해서
끝에서 k번째 노드 찾기를 해보겠습니다.

 

https://yoonkies.tistory.com/7

 

연결 리스트 코드는 여기를 참고해주시면 되겠습니다.

연결 리스트의 끝에서 k번째 찾기

class kFromLast(LinkedListFIFO):           # 기존의 LinkedListFIFO를 상속합니다.
    def find_k_from_last(self, k):
        p1, p2 = self.head, self.head    # p1으로 리스트 전체를 탐색하고 k만큼 차이가 날때 p2로 탐색 시작
        i = 0

        if k <= self.length:     # k값이 잘못 입력되는 경우 방지
            while p1:
                p1 = p1.pointer
                if i >= k:      # k만큼 차이가 났을 때 p2도 다음 노드로 탐색 시작
                    p2 = p2.pointer

                i += 1

            return p2.value

        else:       # k값이 잘못될 경우 다음 문장을 출력 후 None을 반환
            print("Wrong k!")
            return None

# 결과 확인
if __name__ == "__main__":
    ll = kFromLast()
    k = 3

    for i in range(10):
        ll._push(i+1)

    ll._printList()
    print("연결 리스트 끝에서 {0}번째 값은 {1}입니다.".format(k,ll.find_k_from_last(k)))


    # > 연결 리스트 끝에서 3번째 값은 8입니다.

연결 리스트 값 기준 분할하기

만약, 숫자가 담긴 연결 리스트에서 한 항목을 선택했을 때
그 항목의 값의 왼쪽에는 그보다 작은 숫자 항목만 나오고 오른쪽에는 큰 숫자 항목만 나오도록 연결리스트를 구현해보겠습니다.

분할 전:
6 7 3 4 9 5 1 2 8

분할 후:
3 4 5 1 2 6 7 9 8

위와 같이 기존에 작성한 LinkedListFIFO 클래스를 사용하겠습니다.

연결 리스트 분할하기

def partList(ll, n):
    less = LinkedListFIFO()
    more = LinkedListFIFO()
    node = ll.head
    same = 0                  # 만약 n값이 중복 여부

    while node:
        item = node.value
        # n값보다 큰 값은 more에 n값보다 작은 값은 less에 삽입
        if item < n:
            less._push(item)

        elif item > n:
            more._push(item)

        else:              # n값이 중복될 경우 나중에 연속으로 삽입하기 위해 n값의 갯수만큼 same 증가
            same += 1

        node = node.pointer

    for _ in range(same):     # less 뒤에 n값 삽입, 중복된 수 만큼 연속으로 리스트에 삽입
        less._push(n)

    nodemore = more.head

    while nodemore:           # more의 노드값을 less 뒤에 삽입
        less._push(nodemore.value)
        nodemore = nodemore.pointer

    return less


# 결과 확인
if __name__ == "__main__":
    ll = LinkedListFIFO()
    for i in [6, 7, 3, 4, 9, 5, 1, 2, 8, 4]:
        ll._push(i)
    print("분할 전 : ", end = "")
    ll._printList()                        # 분할 전 : 6 7 3 4 9 5 1 2 8
    new_ll = partList(ll, 4)
    print("분할 후 : ",end = "")
    new_ll._printList()                    # 분할 후 : 3 4 5 1 2 6 7 9 8

이상으로 연결 리스트를 가지고 응용을 연습해보았습니다.