[알고리즘/자바스크립트] 뒤집어진 연결 리스트 (Reverse Linked List)

Reverse Linked List

Write a function that reverses the order of a singly-linked list in place.

 

So a list like this:

A -> B -> C -> null

 

Should be transformed into a list like this:

C -> B -> A -> null

 

Example)

var root = Node('A');
var nodeB = root.next = Node('B');
var nodeC = nodeB.next = Node('C');
// The list looks like this: A -> B -> C -> null

var newRoot = reverseLinkedList(root);
// The list now looks like this: C -> B -> A -> null

newRoot.value // => 'C'
newRoot.next // => nodeB
root.next // => null (the old root is now the terminal node)

(You can assume that the list ends without a cycle.)

 

---

 

var Node = function(value){
  return { value: value, next: null };
}
node = Node(5);
node.next = Node(3);
node.next.next = Node(0);
reverseNode = reverseLinkedList(node);

위와 같이 간단하게 생긴 연결 리스트를 만들어서 

reverseLinkedList()함수에 파라미터로 전달하면 

말 그대로 리버스 시키는 문제이다.

 

---

 

 

일단 처음에 푼 방법은 이렇다.

우선 while문으로 맨 마지막 node를 찾는데, 마지막 node를 찾기 위해

head부터 tail까지 순회하는 동안 각 node를 배열에 push한다.

 

while문을 끝내면 node 변수에는 맨 마지막 노드가 담긴다.

이제 아까 만들어둔 배열을 역순으로 순회하면서

맨 마지막 노드의 next에 하나씩 연결하고

배열에 든 가장 마지막 노드의 next에는 null을 넣는다.

 

var reverseLinkedList = function (node) {
  var nodeData = [];
  
  while (node.next) {
    nodeData.push(node);
    node = node.next;
  }
  
  let lastNode = node;
  for (let i = nodeData.length - 1; i >= 0; i--) {
    lastNode.next = nodeData[i];
    if (i === 0) {
      nodeData[i].next = null;
    }
    lastNode = lastNode.next;
  }
  
  return node;
}

 

---

 

위 방법으로 하면 되긴 하는데

문제는 배열같은 다른 메모리 공간을 사용하지 않고 문제를 풀어야한다는 것이다ㅜㅜ...

 

var reverseLinkedList = function (node) {
  let result = null;
  
  while (node) {
    if (!node.next) {
      node.next = result;
      result = node;
      break;
    }
    
    let nextStep = node.next.next;
    let swap = node.next;
    node.next = result;
    swap.next = node;

    result = swap;
    node = nextStep;
  }
  
  return result;
}

 

주말동안 고민고민해서 다시 풀어보았다! 이번에는 배열을 사용하지 않고 풀었는데

result의 초기값으로 null을 넣고 while문으로 반복을 돌리는데

node.next의 값을 swap 변수에 저장해놓고 node.next를 result값으로 덮어쓴다.

 

그리고 swap 변수에 저장해둔 node.next의 next를 node로 바꾼다.

그러면 일단 첫번째 요소와 두번째 요소가 바뀐다.

그리고 세번째 요소는 nextStep에 미리 저장해뒀는데

node 변수에 nextStep을 넣고 다시 반복문을 돌린다.

 

만약에 node의 next가 null이라면 node의 next에 result를 넣고 result에 node를 넣어 break한다.

 

 

---

 

var reverseLinkedList = function (node) {
  let head = node;
  let tail = null;

  while (head) {
    let swap = head.next;
    head.next = tail;
    tail = head;
    head = swap;
  }

  return tail;
}

 

그리고 내가 푼 방법보다 백배 간단한 방법이 있었다(!) ㅠㅠ...

너무 간단해서 허무할 지경...또르르...

 

처음에 head라는 변수를 만들고 거기에 node를 할당한다.

tail 변수에는 null을 넣어둔다.

 

head가 true가 아닐때까지 while문을 돌린다.

swap 변수에 head의 next를 담아두고

head의 next는 tail로 담는다.

tail에는 다시 head를 담는다.

head에는 swap변수에 넣어둔 head를 담는다.

 

head가 null이 되면 반복문을 빠져나오고

tail를 리턴한다.