[LeetCode] Reverse Linked List (JS)

문제

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

 

주어진 단일 연결 리스트를 반대로 뒤집고 그 값을 return 하라 

 

풀이 

출처 : How To Reverse A Linked List With Animated ExamplesMike CroninMike Cronin

 

단일 연결 리스트는 Data와 Next 값만 포함하고 있다.

그렇다면, 어떻게 연결 링크를 이전 노드의 값을 참조할 수 있을까.

 

방법은 생각보다 단순하다. 

바로, 세개의 포인터(prev,curr,next)를 활용하여 연결관계를 바꿔주면 된다. 

 

최초에 변수 설정(포인터)는 다음과 같다.

let prev = null;
let curr = head;
let next;

 

현재를 나타내는 포인터 curr가 head에 있고. 

바로 전 노드 prev 위치를 null로 설정해준다.

 

while(curr) {
    next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}

 

1. curr가 존재하는 동안 loop를 돌린다.

2. curr.next를 prev로 바꿔 연결관계를 반대 방향으로 설정한다.

3. 연결 방향을 수정했다면 prev는 현재의 curr로 curr는 next로 포인터를 옮겨준다

 

답안

var reverseList = function(head) {
	let prev = null;
    let curr = head;
    
    while(curr) {
    	let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
}

시간/공간 복잡도

시간 복잡도  : O(n)

해당 알고리즘는 각 노드를 한 번씩 통과하며 연산을 수행하기 때문에 O(n)이며, 여기서 n은 연결된 노드의 수이다.

 

공간 복잡도 : O(1)

별도의 공간 할당 없이 prev, curr, next라는 변수를 사용하여 기존 공간을 활용하기 대문에 공간 복잡도는 입력 크기에 따라 달라지지 않는 O(1)이다.