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

문제에 대한 이해

주어진 Linked List를 반대로 뒤집는 문제입니다.

경계조건 및 Input, Output 생각해보기

경계조건
input된 값이 null이면 return 합니다.

Input, Output
Input : [1, 2, 3]
Output : [3, 2, 1]
Input : [4, 2, 7, 1, 3]
Output : [3, 1, 7, 2, 4]

수도코드를 작성

// 1. reverseFunc 함수를 만듭니다. 
// 이 함수는 재귀를 실행하는 함수 입니다.
// Input으로는 ListNode를 두 개 받습니다.
// 명칭은 각각 prevNode, nextNode로 짓습니다.

// 2. reverseFunc 함수의 역할은 말 그대로 '뒤집는' 역할입니다.
// ListNode는 val, next로 이루어지는데,
// prevNode의 val를 nextNode의 next에 할당합니다.

// 예를 들어서 [1,2,3]이 있다고 합시다.
// 처음에는 null과 val가 1인 node를 reverseFunc에 넣습니다.
// val가 1인 node의 next는 val가 2인 node를 가리키고 있습니다.
// 이 next에 null을 할당합니다.
// 그리고 reverseFunc에 val가 1인 node와 val가 2인 node를 넣습니다.
// 앞서 작동한 로직이 그대로 작동됩니다.
// 2인 node의 next는 3을 가리키고 있는데, 1인 node를 할당해 줍니다.

// 3. reverseFunc를 재귀적으로 호출합니다.

// 4. 탈출 조건으로는 nextNode가 null이면 return 해줍니다.

코드 작성하기

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseList(head: ListNode | null): ListNode | null {
    if(!head) return null;

    const reverseFunc = (prevNode: ListNode | null, nextNode: ListNode | null): ListNode | null => {
        if(!nextNode) return prevNode;

      	// 재귀적으로 reverseFunc을 호출하는 과정에서 
        // nextNode의 next를 저장할 필요가 있어서 변수를 추가했습니다.
        const originalNext = nextNode?.next;
        nextNode ? nextNode.next = prevNode : null;
        
        return reverseFunc(nextNode,originalNext);
    }

    return reverseFunc(null, head);
};

마무리

재귀 유형을 잘못 풀어서 이번 문제를 선택했습니다. Easy이지만 잘 못하는 유형이라서 2시간 가량 걸렸습니다. 반복문을 선택할지 고민도 했었는데 재귀를 연습하는 차원에서 이렇게 풀었습니다.
수도 코드에서 최대한 상세하게 재귀 함수를 작성하고, 그 부분을 그대로 구현하고자 고민을 하다 보니 다음과 같은 코드를 완성했습니다.