Reverse Linked List

206. Reverse Linked List

Level: Easy

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

Language: C++

/**
 * 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) {
        ListNode* prevNode = NULL;
        ListNode* nextNode = head;
        
        while (head) {
            nextNode = head;
            head = head->next;
            nextNode->next = prevNode;
            prevNode = nextNode;
        }
        return nextNode;
    }
};

time: O(n), space: O(1)

 

위와 다르게 recursive 로 해결하는 방법은 time, space 둘 다 O(n) 이었다.

바로 전 학기에 자료구조 재수강에서 reverse 하는 것을 했었기에 기억을 더듬고 이중연결리스트를 5개 정도 그리면서 대충 말이 되게 만들었다. ㅎㅎㅎ 이거 못 풀면 그냥 (죽어야되는데) ㅎㅎㅎㅎㅎ 다행히 풀었다.. 열심히해야지...