206-gusrb3164.md

1. Reverse Linked List

solution 1

시간복잡도 : O(N)

알고리즘 : 재귀, 백트래킹

풀이 설명 : 연결리스트의 끝부분부터 연결하기 위해 재귀방식으로 현재노드인 node 의 next 부터 next 연결리스트에 저장하고, 거기서 분리된 거꾸로 연결된 노드인 prev 를 전달하는 방식으로 백트래킹을 구현합니다.

소스코드 : link

/**
 * 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) {
        return reverse(head);
    }
    ListNode* reverse(ListNode* node, ListNode* prev=nullptr){
        if(node==nullptr){
            return prev;
        }
        ListNode* next=node->next;
        node->next=prev;
        return reverse(next,node);
    }
};

solution 2

시간복잡도 : O(N)

알고리즘 : 반복

풀이 설명 : 재귀로 구현된 구조를 반복문으로 단순 구현한 구조입니다. prev 에 reverse 방식으로 연결된 연결리스트, next에 현재 노드를 prev에 붙이고 다음 탐색을 위해 남겨진 연결 리스트, node에 현재 탐색하고 있는 노드의 정보를 저장합니다. node-> next에 prev를 연결하여 현재까지의 역순을 저장한 뒤, 다시 prev 에 새로 갱신된 역순을 저장하고, node 는 그다음 역순으로 연결할 노드를 저장합니다.

소스코드 : link

/**
 * 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* node=head;
        ListNode* prev=nullptr;
        while(node!=nullptr){
            ListNode* next=node->next;
            node->next=prev;
            prev=node;
            node=next;
        }
        return prev;
    }
};