Linked List를 뒤집기(Reverse Linked List)

Published in

Hello, world?

4 min readAug 23, 2020

leetcode의 Reverse Linked List 문제를 풀면서 이해가 되지 않았던 부분들이 많았다. 공부한 것을 정리하고, 다른 누군가에게도 도움이 되고자 풀이과정을 적어보려고 한다.
https://leetcode.com/problems/reverse-linked-list/submissions/

단방향 linked list를 뒤집는 문제로 Input: 1->2->3->4->5->NULL라면 Output: 5->4->3->2->1->NULL으로 나오게 바꾸면 된다.

즉 {value:1, next: { value:2, next:{value:3, next: null}}}을 {value:3, next: { value:2, next:{value:1, next: null}}}로 뒤집어서 리턴한다.

전체 코드는 아래와 같다.

const reverseLinkedList = function(node) {  
  let prev = null;        //1
  let next;               //2
            
  while(node){            //3 
    let swap = node.next; //4    
    node.next = prev;     //5
    prev = node;          //6
    node = swap;          //7
  }  
  return prev;            //8
}

기존의 linked list를 뒤집어야하므로 화살표의 방향이 바뀌어야하고, 그러한 과정에서 기존에 next로 설정되어 있던 값을 미리 특정 변수에 넣어두고, 사용할 수 있도록 한다.

1-> 2 -> 3-> null 즉 node 개수가 3개일 때를 예시로 들어보면 node는 head, prev는 null인 상태로 시작한다.

우선 첫 번째 사이클을 돌려본다.

주석3 while(node) node는 head이므로 true이고 반복문이 돌아갈 수 있다.
주석4 let swap = node.next node.next 즉 swap은 2를 가리킨다.
주석5 node.next = prev node.next에 prev를 넣으므로 화살표의 방향이 바뀐다. 그리고 주석1 let prev = null을 통해 node.next는 null이 될 것이다. 즉, node.next = prev = null이므로 node.next === null
주석6 prev = node 이제는 주석5에서 기존에 null로 설정된 prev를 이용하는 것과 달리 prev에 node라는 값을 설정해주는 차례이다. (개인적으로 이 부분에서 가장 헷갈렸다.) 전제조건에 따라 node는 head이므로 1을 가리키고, prev또한 1을 가리킨다. 즉, prev = node = 1이므로 prev === 1
주석7 node = swap swap이라는 변수는 2로 설정되었으므로 node는 2를 가리킨다. 즉, node === 2

두 번째 사이클을 돌려보면 prev는 2, node는 3이 된다.

세 번째 사이클을 돌려보면 prev는 3, node는 null이 된다

세 번째를 통해 node가 null이 되었기에 더 이상 주석3 while(node)은 반복문을 돌 수 없다. 이러한 과정을 거쳐서 reverse된 Linked List가 생기고, return prev 하면 된다. 그리고 재귀로 풀 수도 있기에 그것 또한 추가적으로 업데이트를 할 예정이다.

Update 재귀로 푸는 방법

const reverseList = function(head){
  if(!head || !head.next) return head;
  let reversed = reverseList(head.next);//주석1
  head.next.next = head;//주석2
  head.next = null;//주석3
  return reversed;
}

우선 1->2->3->4까지 반복적으로 잘 진행이 된다. 그 후 5.next가 null이 되면서 주석2와 주석3을 통해 기존에 ->로 진행되었던 방향을 <-로 바꿔준다.
그렇게 바꿔준 것들을 토대로 다시 head.next로 reverseList함수를 진행한다.

Linked List를 뒤집기(Reverse Linked List)

Written by Sunmin