206. Reverse Linked List

https://leetcode.com/problems/reverse-linked-list/

 

주어진 LinkedList 를 Reverse 하는 문제.

복잡한 문제 같지만 천천히 생각해보면 그렇지 않다.

1) 첫번째 직관적인 솔루션
    Prev라는 이전 노드를 저장하는 노드를 정의.
    1 -> 2 -> 3 이라는 리스트가 있다면,
    Prev = nullptr 일때, head = 1 
    Prev = 1 일때, head = 2
    Prev = 2 일때, head = 3
    Prev = 3 일때, head = nullptr이 된다.
    즉 새로운 Prev = head가 되고, 새로운 Prev의 next 는 Prev가 된다.
    여기서 나는 tp라는 새로운 노드를 만들었고, tp 는 새로운 Prev 노드인데
    이는, head->val의 값을 갖고 현재 prev를 next에 저장한다.
    그리고 head 를 이동시켜준다.

이는 새로운 tp라는 노드를 할당하고 기존 linkedlist의 노드를 활용하지 않기에, 공간 효율이 좋지 않다.

2) 두번째 공간 개선

새로운 공간을 할당하지않고, 기존 노드를 사용하는 방법이다.
TP라는 pointer는 head->next에 대한 정보를 들고 있고,
새로운 head->next 를 prev로 저장, 새로운 prev를 next가 바뀐 head로 업데이트.
다음 while loop를 위해, 기존 head->next에 대한 정보를 head에 다시 저장해주기.