[LeetCode] Reverse Linked List (C++)

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

Reverse Linked List - LeetCode

연결리스트의 참조 방향을 바꾸는 문제였습니다. iterator와 recursive 두가지 풀이 방식이 존재합니다.

 

iterator

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

/* 
 * iterator
 * https://www.youtube.com/watch?v=NhapasNIKuQ
 * recursive
 * https://www.youtube.com/watch?v=MRe3UsRadKw
*/


class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode* prev = NULL;
        
        while(head) {
            ListNode* tail = head->next; // head의 다음이 tail
            head->next = prev; // prev가 head의 다음
            prev = head; // head가 prev
            head = tail; // tail이 head
        }
        
        return prev;
    }
};

 

  ListNode* reverseList(ListNode* head) {
        
        ListNode* prev = NULL;
        
        while(head) {
            ListNode* tail = head->next; // head의 다음이 tail

 

 

head->next = prev; // prev가 head의 다음

 

 

 prev = head; // head가 prev
 head = tail; // tail이 head
 
 ....
 
 // while문이 반복됨
  while(head) {
            ListNode* tail = head->next; // head의 다음이 tail
            head->next = prev; // prev가 head의 다음
            
            
            ....

 

 

위와 과정을 반복하면 최종적으로 다음과 같은 모양이 형태가 되고, 연결리스트 prev가 Reverse Linked List가 됩니다. 따라서 prev를 리턴해주면 문제가 해결됩니다.

 

recursive