[Easy] 206. Reverse Linked List

문제

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

예시

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

 

제약조건

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

풀이 과정

단일 연결 리스트를 반전시키는 문제였다. 

처음 아이디어는 연결리스트의 tail 부분을 찾아가서 next를 prev로 주는 거였는데,

후속 조치 중 iteratively or recursively가 있어 재귀로 해결해보았다.

 

• input head가 falsy라면 null를 반환한다.
• next가 prev를 가리키는 새로운 node를 생성한다.
• head.next가 존재한다면 reverseList 함수를 재귀 호출한다. 이때 첫번째 인자에는 head.next가 들어오고, 두번째 인자에는 새롭게 만든 node를 넣는다.
• node는 prev node의 역할이지만, 새롭게 만들어지는 node에서 prev가 next로 바뀌게 된다.
• 연결 리스트 순회를 마쳤다면 node를 반환한다.
• node는 원래 존재하는 origin-node에서 next가 prev로 바뀐 node이다. 
• 연결 리스트 순회가 마칠 때까지 재귀가 돌고, 순회가 끝나면 맨 마지막 node부터 반환이 되기 때문에 순서가 반전된다. (재귀 함수 호출은 stack에 쌓이고 LIFO 순으로 호출 된다.)

풀이 코드

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head, prev = null) {
    if(!head) return null;
    
    let node = new ListNode(head.val, prev);
    return head.next ? reverseList(head.next, node) : node;
    
};