프린세스 다이어리

[LeetCode] Reverse Linked List - 자바스크립트 풀이 본문

자료구조, 알고리즘

[LeetCode] Reverse Linked List - 자바스크립트 풀이

개발공주 2021. 11. 30. 12:18
728x90

 

1. 접근 방법

(1) 리스트의 끝까지 재귀로 타고 들어간 다음, 끝에서부터 하나씩 돌아오면서 역순으로 노드를 연결해준다.

 

(2) head.next가 마지막 노드인 경우는 head.next가 아무것도 가리키지 않는 상태이므로 head.next.next === NULL 이라고 볼 수 있다. 이 head.next를 이전 노드, 즉 head를 가리키도록 한다.

    head.next.next = head;

 

(3) head는 더이상 head.next를 가리킬 필요가 없으므로 연결고리를 끊어준다.

    head.next = null;

 

(4) 해당 단계를 마치면 이전 재귀 단계로 한 단계 돌아와 같은 방법으로 수행한다.

 

2. 전체 해답

/**
 * 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) {
    if (!head || !head.next) return head;
    
    const answer = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return answer;
};

https://bcp0109.tistory.com/142 이 글을 보고 간신히 이해했다. 감사합니다..

 


다른 풀이

/**
 * 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 prev;
    
    let temp = head.next;
    head.next = prev;
    return reverseList(temp, head);
};

 

 

728x90
Comments