206. Reverse Linked List

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

 

연결리스트 뒤집는 문제.

 

---

 

1. 문제 이해

 

 

=> Given the head of a singly linked list, reverse the list, and return the reversed list.

단일 연결리스트의 헤드 노드가 주어질 시, 연결리스트를 뒤집어서 리턴하라.

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

재귀적인 방법만 써보게쓰.

 

---

2. 문제 재정의

 

요구 사항이 간단 명료해서 따로 문제 재정의는 스킵하겠다.

 

---

3. 계획 수립

 

각 노드를 재귀적으로 돌면서, 현재 노드의 다음 노드가 현재 노드를 가르키게 하면 된다.

그리고 값을 전달 전달받아서, 최종적으로는 맨 끝 노드를 반환하게 하면 된다!  

 

 

 

---

4. 계획 검증 

 

재귀 탈출 조건으로 현재 노드가 NULL이거나, 현재 노드의 next가 NULL이면 마지막 노드이므로 현재 노드를 리턴.

따라서 노드가 0개일 경우도 만족. 최대인 5000개 일 경우에도 10개인 경우와 차이가 없음. 

 

---

 

5. 프로그램 구현 

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;
        ListNode *last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
    
        return last;
    }
};

 

---

 

 

6. 피드백 & 복기

 

재귀 다시 공부해야겠다.

 

ListNode *last = reverseList(head->next);

...

return last;

 

이렇게 처리해줄 시, 맨 끝 노드를 전달 전달하여 최종적으로 반환하는 아주 기본적인 사실을 기억하지 못했다. 이것 때문에 몇시간 날렸다..ㅠㅠ