[LeetCode] Reverse Linked List

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

Reverse Linked List - LeetCode

주어진 링크드 리스트를 뒤집는 문제이다. 스택을 이용하면 간단한 로직으로 풀 수 있다. 처음엔 prev를 생각했다가 스택이 더 쉽게 구현이 가능할 것 같아서 방향을 틀었다. 푼 이후에 보니 prev보다 스택이 시간초가 더 빨랐다.

다만 ListNode*를 계속 재사용했더니 Use After Free 이슈가 발생했다. 검색을 통해 왜 발생하는지(Heap에서 공간을 해제한 후에 재할당하면, 이전 주소가 남아있는 이슈이다)는 알았으나 해당 풀이에서 왜 발생했는지는 아직 정확하게는 잘 모르겠다. 학부 4년을 썼지만 포인터는 아직도 잘 모르겠다 ㅠㅠ

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr)
            return nullptr;
        if(head->next==nullptr)
            return head;
        stack<ListNode*> s;
        ListNode* temp = head;
        
        while(temp->next!=nullptr) {
            s.push(temp);
            temp=temp->next;
        }
        ListNode* result=new ListNode(temp->val);
        temp=result;
        while(!s.empty()) {
            temp->next= new ListNode(s.top()->val);
            temp=temp->next;
            s.pop();
        }
        return result;
    }
};