Approach

• head 또는 head->next 값이 NULL이면 요소의 개수가 0 또는 1이기에 바로 return
• ListNode reverse를 하나 만든다.
• 현재 head 노드가 NULL이 아니라면 노드 끝까지 탐색한다.
• head의 다음 노드를 담아둘 ListNode next를 생성한다.
• 현재 head 노드에서 다음 next 노드를 reverse에 연결한다.
• 그리고 reverse는 head로 바꾼다.
• 위의 과정을 거치면 head가 1일때 reverse(NULL)을 가리키고 reverse는 head = 1, head->next = NULL 인 현재 head로 바꾼다. 이를 반복하면 head가 2일때는 reverse(val = 1)을 가리키고 reverse는 head(val = 2), head->next -> reverse(val = 1)인 노드로 바뀌게 된다.

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) {
        if(head == NULL || head->next == NULL) return head;

        ListNode* reverse = NULL;

        while(head != NULL)
        {
            ListNode* next = head->next;
            head->next = reverse;
            reverse = head;
            //cout << reverse->val << "\n";
            head = next;
        }

        return reverse;
    }
};

Result

---

추가적인 해결방법

• 재귀 특성을 이용

  class Solution {
  public:
      ListNode* reverseList(ListNode *head, ListNode *nextNode = NULL, ListNode *prevNode = NULL) {
          return head ? reverseList(head->next, (head->next = prevNode, nextNode), head) : prevNode;
      }
  };