단방향 링크드 리스트 뒤집기 - 파이썬 (Python)

링크드 리스트 정리

https://seongonion.tistory.com/20?category=867075 

링크드 리스트의 구현 및 연산 - 파이썬(Python)

 

우선, 단방향 링크드 리스트를 클래스를 통해 간단히 구현해보자.

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

각 노드들은 data와 next를 속성으로 가질 수 있다.

 

링크드 리스트는 다음과 같이 구현해줄 수 있도록 하고, 각 노드를 순회할 수 있는 circuit 함수를 구현해주었다.

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def circuit(self):
        node = self.head

        while node:
            print(node.data, end=' ')
            node = node.next

node_1 = Node(1)
node_2 = Node(2)
node_3 = Node(3)

linked_list = SinglyLinkedList()

linked_list.head = node_1
node_1.next = node_2
node_2.next = node_3

이후, 세 개의 노드를 만들고 각 노드들을 연결해준 후, 첫 번째 노드를 링크드 리스트의 head에 넣어준다.

 

이후, 해당 리스트를 circuit해주면 다음과 같이 나온다.

 

이제, 이 노드들을 한 번 뒤집어보자.

 

class SinglyLinkedList:

    def reverse(self):
        node = self.head
        if node == None:
            return None
        
        tmp = []
        while node:
            tmp.append(node)
            node = node.next
            cnt += 1

        for i in range(len(tmp)-1, 0, -1):
            tmp[i].next = tmp[i-1]
        
        tmp[0].next = None
        self.head = tmp[-1]

가장 단순한 생각은 각 노드를 모두 리스트에 저장해준 후, 해당 리스트를 거꾸로 돌면서 순서를 정해주는 방법이다.

 

리스트가 정상적으로 뒤집힌 것을 알 수 있다.

 

하지만, 이러한 방식은 링크드 리스트를 두 번 순회해야한다는 단점이 있다.

 

사실, 시간복잡도 측면에서 O(n)이나 O(2n)이나 동일하게 O(n)으로 취급하지만, 한 번만 순회해서 해결할 수 있는 문제라면 당연히 그렇게 해결하는 것이 바람직하다.

 

반복문을 한 번만 사용

머리 속에서는 구현이 되는데, 이게 실제 코드로 작성하려면 여간 머리 아픈게 아니다.

 

접근법 자체는 피보나치 수열을 반복문으로 구현하는 것과 유사하다.

 

먼저, 현재 노드와, 그 이전 노드, 그리고 다음 노드. 이렇게 3개를 각각 변수에 지정해주고 해당 값들을 스왑해주며 문제를 해결할 수 있다.

class SinglyLinkedList:
    
    def reverse(self):
        node = self.head
        prev = None

        while node:
            tmp = node.next
            if tmp == None:
                self.head = node
                
            node.next = prev
            prev = node
            node = tmp

가장 중요한 것은 변수들을 저장해주는 순서이다. 

 

먼저, 현재 노드와 해당 노드의 next 값이 될 prev를 정의해준다. 기존 head의 next 값은 None이 되어야하므로, prev는 우선 None으로 정의해준다.

 

1. while문을 돌면서 현재 노드의 next를 tmp에 저장해준다.

2. 현재 노드의 next를 prev 값으로 바꿔준다.

3. prev의 값을 현재의 노드로 바꾸어준다. (다음 노드의 next가 될 것이기 때문)

4. node를 처음에 저장해 두었던 tmp로 바꾸어준다. (노드의 기존 next 값)

 

순회 시 self.head부터 차례대로 도는 것을 유지하기 위해서 while문 안에 tmp가 None 값일 때 (node.next가 None일 때) 현재의 노드 값을 self.head에 저장해준다.

 

linked_list.reverse()
linked_list.circuit()

링크드 리스트를 뒤집은 후 circuit 하도록 하면 값이 잘 뒤집어진 것을 확인할 수 있다.