[ leetcode 문제풀이 ] Reverse Linked List

Reverse Linked List - LeetCode

Reverse Linked List - LeetCode

(Reverse Linked List 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Reverse Linked List 문제 설명 >

 

Reverse Linked List 문제는 다음과 같다.

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

 

singly linked list의 head가 주어질 때, list를 뒤집고(연결관계를 반대로) reversed된 list를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한조건은 다음과 같다:

linked list의 노드의 개수는 [0, 5000] 범위 내에 있다.

-5000  ≤  Node.val  ≤  5000

 

Follow up question: linked list는 iteratively, recursively 두 방식으로 reversed 될 수 있는데, 두 방식 모두 적용해보아라.

 

 

 

---

< Reverse Linked List 문제 접근(1) >

 

먼저 iteration을 사용해 풀어보았다. (Cpp 사용)

 

#include <algorithm>

ListNode* reverseList(ListNode* head) {
    if(head == nullptr) return head;
    if(head->next == nullptr) return head;
        
    ListNode *pointNow = head->next, *pointNext = head;
    head->next = nullptr;
    while(pointNow != nullptr){
        pointNext = pointNow->next;
        pointNow->next = head;
        head = pointNow;
        swap(pointNow, pointNext);
    }
    return head;
} // runtime : 12 ms (faster than 30.58 %), memory usage : 8.3 MB (less than 80.59 %)
// linked list is reversed iteratively

 

pointNow : 수정을 진행하는 현재 노드 / pointNext : 다음으로 수정을 진행할 노드

line 9 : 현재 노드가 nullptr일 경우 linked list의 끝에 도달한 경우임

line 10 : pointNow node를 수정하면 기존에 연결된 다음 노드에 접근할 수 없으므로

pointNext에 기존에 연결된 다음 노드를 저장.

line 11, 12 : 현재 노드의 next 노드를 head로 수정. head를 현재 노드로 교체

line 13 : pointNext(다음으로 수정을 진행할 노드)를 pointNow와 swap

 

 

 

---

< Reverse Linked List 문제 접근(2) >

 

ListNode* reverseList(ListNode* head) {
    if(!head || !(head->next)) return head;

    ListNode* pointNode = reverseList(head->next);
    (head->next)->next = head;
    head->next = nullptr;
    return pointNode;
} // runtime : 4 ms (faster than 94.30 %), memory usage : 8.5 MB (less than 20.34 %)
// linked list is reversed recursively

 

recursion을 사용한 방식은 헤메대가 discussion을 보고서야 코드를 다듬을 수 있었다...

recursion을 이용해 하위문제부터 탐색하고자 한다면 함수 중간에 재귀를 써주면 된다.(그동안 잘 못 활용하고 있었다)

머리속에서 부분 문제가 잘 안떠오르는 느낌이라 해야하나...

 

이렇게 또 하나 배우고 갑니다.