[C++] [LeetCode 206] Reverse Linked List

---

문제 풀기 전 생각 : 

/*
링크드 리스트 iterator 를 사용한 반복문으로
현재 노드의 다음 노드의 포인터를 저장하고
현재 노드의 연결고리를 끊고 전 노드와 연결
그리고 전 노드를 현재 노드로 변경 작업을 
모든 노드를 거칠 때까지 반복
*/

---

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=head, *prepre= NULL;
        if(head == NULL) return head;
        for(ListNode* ln = head->next ; ln != NULL ; ln = ln->next){
            pre->next = prepre;
            prepre = pre;
            pre = ln;
        }
        pre->next = prepre;
        return pre;
    }
};

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

Reverse Linked List - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

 

링크드 리스트의 연결을 뒤집는 작업이 

오랜만이라 잠시 멍 했던거 같다

그래도 문제가 뚫어져라 쳐다보니 

이해가 되서 풀 수 있었다

---

개선방안 :

class Solution {
public:
    // Method 1: Iterative
    /*
    ListNode* reverseList(ListNode* head) {
        if (head==nullptr)
            return head;
        ListNode *prev=nullptr, *next=nullptr;
        while (head!=nullptr){
            next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
    */
    
    // Method 2: Recursive
    ListNode* reverseList(ListNode* head) {
        if (head==nullptr || head->next==nullptr)
            return head;
        ListNode *p = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return p;
    }
};

오호 재귀함수로 푼 버전도 흥미롭다

코드가 직관적이라 이해하기 편한것 같다