(Leet Code c++)Reverse Linked List

206. Reverse Linked List

 

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

 

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

 

Constraints:

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

주어진 Linked List를 반대로 만들어서 리턴해야 한다.

스택을 이용해 Linked List를 저장한다.

head가 마지막 노드에 향하게 된다면 스택에서 다시 꺼내 거꾸로 연결 시키면 된다.

 

스택에서 꺼낸 노드의 next가 남아있기 때문에 이를 NULL로 만든 후, 연결을 시켜주면 된다.

/**
 * 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) {
        stack<ListNode*> stk;
        ListNode * current;
        
        while(head != NULL && head->next != NULL){
            stk.push(head);
            head = head->next;
        }
        
        current = head;
        
        while(!stk.empty()){
            ListNode * tmp = stk.top();
            stk.pop();
            
            tmp->next = NULL;
            current->next = tmp;
            current = current->next;
        }
        
        return head;
    }
};