[LeetCode] 206. Reverse Linked List

 

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

Leetcode - Reverse Linked List

문제 유형 : 연결리스트

문제 난이도 : Easy

 

문제

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

연결리스트의 head가 주어진다. 연결리스트를 뒤집어서 반환하시오.

 

풀이

반복문 또는 재귀로 풀 수 있다.

현재 노드의 포인터와 이전 노드에 대한 포인터가 필요하다.

재귀의 경우, 먼저 끝에 도달해서 head를 새로 찍은 다음에, 연결을 반대로 이어주면 된다.

반복문을 이용할 경우도 같다. 다음 노드의 포인터를 미리 찍어두고, 현재 노드의 다음을 이전 노드로 설정한다.

 

코드

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 {
private:
    ListNode* head;
public:
    void reverse(ListNode* curr, ListNode *prev) {
        if(curr == NULL) {
            this -> head = prev;
            return;
        }
        reverse(curr -> next, curr);
        curr -> next = prev;
    }

    ListNode* reverseList(ListNode* head) {
        reverse(head, NULL);
        return this -> head;
    }
};