206. Reverse Linked List

문제링크: https://leetcode.com/problems/reverse-linked-list/

주어진 연결 리스트의 역순을 반환하는 문제다.

Solution 1

Iteration & New List

먼저 가장 간단한 방법으로 반복을 통해 주어진 연결리스트를 순회하고 새로운 리스트를 만드는 방법이다.

Alogorithm

• 주어진 연결 리스트를 앞부터 순회한다
• 해당 리스트의 val을 카피해 새 노드를 만들고 역순으로 연결시킨다.
• 새 노드를 만드는 만큼 공간복잡도가 O(n)이 생긴다.

var reverseList = function(head) {
    if (head === null) return head;
    let result = new ListNode(head.val);
    let cur = head;
    while (cur.next !== null) {
        cur = cur.next;
        const temp = new ListNode(cur.val, result);
        result = temp;
    }
    return result;
};

Solution 2

Iteration & Edit node

노드를 새로 생성하지 않고 기존 노드를 수정한다면 공간복잡도를 최적화 할 수 있다.

Algorithm

• 구조분해 할당의 snapshot원리를 이용
• prev와 curr을 가지고 curr -> prev의 링크를 만들어 준다.
• 대신 다음 iteration을 위해 현재값은 curr.next값으로 갱신, 이때 구조분해 할당의 snapshot을 통해 curr.next값을 보존 후 저장한다.

var reverseList = function(head) {
    let [prev, current] = [null, head];
    while(current) {
        [current.next, prev, current] = [prev, current, current.next];
    }
    return prev;
}