LeetCode 07: Reverse Linked List

문제링크: https://leetcode.com/problems/reverse-linked-list/

Problem

주어진 Linked List의 Reverse List를 구하는 문제이다.

Solution

1) Stack의 자료구조 활용

list를 하나씩 순회하면서 값을 스택에 넣어준 후, 스택의 값을 하나씩 pop하면서 reverse list를 완성해주었다.

그러나 이는 list 순회를 두 번이나 해야하는 방식으로, iterative와 recursion 방식을 사용해서 풀면 문제를 더 효율적이고 간단히 풀 수 있는 것을 확인했다.

2) Iterative Method
노드의 순서를 바꾸는 것이 아닌, 링크의 방향을 바꾸는 방식으로 접근해보자.

예를 들어, 1→2→3의 linked list가 있으면 값의 순서를 3→2→1로 바꾸는 것이 아닌
노드의 값은 유지한채 링크의 방향을 1←2←3으로 바꿔주는 것이다.

1. curr를 head로 두고
2. head를 한 칸 옮긴다. (head와 연결된 노드를 보존하기 위해 아래의 코드를 실행하기 전에 미리 head를 옮겨야 한다!!)
3. curr.next를 prev로 두고, (링크의 방향을 거꾸로 수정)
4. prev를 curr로 두자. (prev를 다음 칸으로 옮기기)

prev = None
while (head):
    curr = head
    head = head.next
    curr.next = prev
    prev = curr

return prev

3) Recursive Method
기존의 함수에 prev를 전달하는 파라미터를 하나 추가하자.

curr를 head로부터 하나씩 옮겨가면서 curr의 next를 prev로 지정해준다.

def reverseList(self, head, prev=None):

    if not head:
        return prev

    curr, head.next = head.next, prev

    return self.reverseList(curr, head)