LeetCode/206.Reverse Linked List

간단히 등장한 순서대로 vector에 저장하고 pop_back 기능을 이용하든 임의접근을 이용하든 해서 새 노드를 하나 만든다음 줄줄이 엮어주면 된다.

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if(head==nullptr)
            return nullptr;
        if(head->next==nullptr)
            return head;
        
        vector<ListNode*> nodes;
        ListNode* cur = head;
        while(true)
        {
            nodes.push_back(cur);
            if(cur->next==nullptr)
                break;
            cur = cur->next;
        }
        
        ListNode* ret = nodes.back();
        ListNode* cur2 = ret;
        
        for(int i=nodes.size()-2; i>=0; --i)
        {
            cur2->next = nodes[i];
            cur2 = cur2->next;
        }
        
        cur2->next = nullptr;
        
        return ret;
    }
};

---

3포인트를 사용한 풀이도 있다.

1. 우선, 나의 다음 녀석을 temp에 저장한다.

2.  그 뒤, 나의 next를 prev로 바꾼다.(연결방향을 거꾸로 돌린다. head라면 prev==nullptr이니 nullptr이 된다.)

3. prev는 현재 나로 바꾼다.

4. 나는 다음 녀석으로 이동

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        if(head==nullptr)
            return nullptr;
        if(head->next==nullptr)
            return head;
        
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* temp = nullptr;
        while(cur)
        {
            temp = cur->next;
            
            cur->next = prev;
            prev = cur;
            
            cur = temp;
        }
        
        return prev;
    }
};