파이썬 연결리스트 — 연결리스트 뒤집기

파이썬 코딩테스트 & 기술면접 뽀개기 (7)

문제

Reverse Linked List - LeetCode

1. 문제분해

input: 연결리스트
ouput: 뒤집어진 연결리스트

2. 패턴인식, 자료 표현

• 뒤집어진다.
• prev → cur → next 인 경우, next → cur → prev
• 각 노드에 대해서, 이렇게 전과 후의 관계를 바꾸어 주어야 한다.
• 연결리스트는 한 방향이니까, 각 노드에 대해 cur → prev 이런식으로 바꾸어주고, 마지막 노드를 리턴한다.

3. 패턴분석, 일반화

• 리스트 노드를 돌아다니면서 계속해서 뒤집기

4. 구현

코드출처: https://github.com/onlybooks/algorithm-interview

이 문제는 반복, 재귀 두가지 방법으로 풀 수 있다.

1. 반복

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None
        while node:
            # 노드를 순회하면서, next 값은 변경시켜 준다.
            # 가변객체의 .next 값은 해당 값
            next_node, node.next = node.next, prev
            # 변수에 새로운 노드 할당
            prev, node = node, next_node
       return prev
# prev, node : 이전노드와 현재노드를 가리키는 포인터
# next_node : 다음 노드로 이동시키기 위한 값

2. 재귀

def reverseList(self, head:ListNode) -> ListNode:
    def reverse(node: ListNode, prev: ListNode = None):
        if not node:
            return prev
        next, node.next = node.next, prev
        return reverse(next, node)
    return reverse(head)