3.4.3 3.4.3

main.py

"""
문제 : 연결리스트 뒤집기

"""


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


def reverseList(head: Node) -> Node:
    prev = None
    curr = head

    while (curr != None):
        next_temp = curr.next

        curr.next = prev
        prev = curr
        curr = next_temp

# 스택을 이용한 방법
def reverseList2(head: Node) -> Node:
    if head == None:
        return head

    stack = []

    curr = head

    while curr.next != None:
        stack.append(curr)
        curr = curr.next

    first = curr

    while stack:
        curr.next = stack.pop()
        curr = curr.next

    curr.next = None

    return first


# 재귀를 이용한 방법

def reverseList3(head: Node) -> Node:
    if head == None or head.next == None:
        return head

    reversed_list = reverseList3(head.next)
    head.next.next = head
    head.next = None

    return reversed_list

if __name__ == '__main__':
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)

    node1.next = node2
    node2.next = node3

    reverseList3(node1)