[LeetCode] 206. Reverse Linked List

LeetCode - 206. Reverse Linked List 알고리즘 문제 풀이

분류

문제 링크 : https://leetcode.com/problems/reverse-linked-list/

풀이

ListNode*에 연결된 노드를 거꾸로 만들어서 반환하는 문제이다.

즉, LI-FO 형태를 갖는 스택 자료 구조를 연결리스트로 구현한 것과 동일한 형태인데, head에 연결된 노드를 차례로 순회하며 newNode에 값(val)을 할당하고 newNode->next가 rev를 가리키도록 만든다. 그리고 rev는 항상 시작 노드를 가리키고 있어야 하므로 rev = newNode가 된다.

소스 코드

/**
 * 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* rev = nullptr;
        for (ListNode* now = head; now != nullptr; now = now->next) {
            ListNode* newNode = new ListNode(now->val, rev);
            rev = newNode;
        }
        return rev;
    }
};