[LeetCode] 206. Reverse Linked List

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

Reverse Linked List - LeetCode

미쳤다.재귀를 이문제를 통해 처음으로 완전히 이해했다!!!재귀가 이런거였군...!!!

개초보인 나에게는 이순간이 너무 감동적이다...

 

먼저, 이문제는 Two Pointer를 사용하는방법과 재귀를 사용하여 푸는 방법 두가지가 존재한다.

Two Pinter는 간단하다.

1.처음 prev는 none,curr은 현재노드를가리킨다. (prev->cur)

2. curr이 있다면 prev<-cur 로순서를 바꾸고, prev와 cur을 한칸씩이동.

---

이제 재귀를 살펴보도록 하자.

재귀에서 가장 중요한것은,문제를 제일작은 단위로 쪼개서 하나씩 경우를 넓혀가는것이다.

아래 그림처럼 먼저 노드가한개일때,두개일때를 고려해본다.

우선 제일먼저 설정해야할 base조건은 curr=null이면 return prev.이다.

그럼 반복되는 것이 보인다. curr!=null이면 한칸씩옮긴후 동일한과정을 반복한다...!

그럼 이부분에 재귀를 걸면된다.

 

 

 

 

---

SOLUTION CODE

1. Two Pointers

# PYTHON Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev,curr = None,head

        while curr:
            nxt=curr.next
            curr.next = prev
            prev=curr
            curr = nxt

        return prev

 

# C++ Code

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

 

2. Recursion

# PYTHON Code

class Solution:
    def reverseList(self, node, prev=None) -> Optional[ListNode]:
        if curr=None:
            return prev
        else:
            next = curr.next
            curr.next=prev
            return self.reverseList(next,prev=curr) # 한칸씩옮겨주기,그리고같은과정반복

 

# C++ Code

/**
 * 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) {}
 * };
 */

ListNode* recursion_func(ListNode* cur,ListNode* prev){
    if(cur == NULL){
        return prev;
    }
    ListNode* next = cur->next; // cur->next임시저장
    cur->next=prev; // prev<-curr
    ListNode* head = recursion_func(next,cur); // 한칸씩 옮겨 같은과정반복(head==prev)
    return head;

}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recursion_func(head,NULL);
    }
};