문제
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
풀이
반복문으로 풀어보기
반복문을 돌면서 각 노드의 prev 포인터를 연결해준다.
한번더 반복문을 돌면서 각 노드의 next포인터를 prev포인터와 일치시킨뒤, head를 맨 마지막 노드를 가리키게 하면 된다.
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
let pointer = head,
last = head;
while (pointer !== null) {
// 포인터 거꾸로도 연결하기
if (pointer.next !== null) pointer.next.prev = pointer;
else last = pointer;
if (!pointer.prev) pointer.prev = null;
pointer = pointer.next;
}
let rpointer = last;
while (rpointer !== null) {
// next포인터를 prev포인터와 일치시키기
rpointer.next = rpointer.prev;
rpointer = rpointer.prev;
}
return last;
};이렇게 풀 경우 O(n)으로 풀 수 있다.
결과
재귀로 풀어보기
재귀 트리에서 내가 어떤 노드에 진입했을때 필요한 정보는 이전 노드의 정보와 현재 노드의 정보이다.
그래야, 현재 노드의 next를 이전 노드로 가리키게 할 수 있기 때문이다.
var reverseList = function(head) {
let last;
const reverse = (prev, cur) => {
if (cur === null) {
last = prev;
return;
}
reverse(cur, cur.next);
cur.next = prev;
};
reverse(null, head);
head = last;
return head;
};
