[DataStructure] reverse linked list

linked list로 만들어진 head를 reverse 하는 방법

Code

codepen에서 테스트 해보자.

let head = {
    value: '1',
    next: {
        value: '2',
        next: {
            value: '3',
            next: {
                value: '4',
                next: {
                    value: '5',
                    next: {
                        value: '6',
                        next: null
                    }
                }
            }
        }
    }
}

let tail = {
  value: '6',
  next: null
}

function reverse() {
    let first = head;
    let second = first.next;
    head.next = null;  	
  	tail = head;
    
    while (second) {
        const temp = second.next;
        second.next = first;
        first = second;
        second = temp;
    }
    
    head = first;
}
reverse();

Code 설명

아래 그림을 참고하면서 단계적으로 설명한다.
그림의 가장 윗부분은 초기상태의 linked list를 나타낸다.

// 먼저 1번째, 2번째 노드를 각각 first, second에 assign한다.
    let first = head; 
    let second = first.next;
// 회색박스 : head.next=null 로 link 연결을 끊는 부분이다.
    head.next = null;
// pointer가 null인 head를 tail에 넣는다.
  	tail = head;

while loop

loop#1

 while (second) {
        const temp = second.next; // 3번 node를 temp에 저장한다.
        second.next = first; // 빨간선 : 2의 pointer(next)를 1로 가리키게 한다.
        first = second; // 초록박스 : 첫번째를 2로 지정한다.
        second = temp; // 파란박스 : second값을 temp로 바꾼다.
    }

loop#2

 while (second) {
        const temp = second.next; // loop#1의 second의 next를 temp에 저장한다. 
        second.next = first; // 빨간선 : 3의 pointer(next)를 2(1번째 루프의 초록박스)로 가리키게 한다.
        first = second; // 초록박스 : 첫번째를 3로 지정한다.
        second = temp; // 파란박스 : second값을 temp로 바꾼다.
    }

loop#3

 while (second) {
        const temp = second.next; // loop#2의 second의 next를 temp에 저장한다. 
        second.next = first; // 빨간선 : 4의 pointer(next)를 3(loop#2의 초록박스)로 가리키게 한다.
        first = second; // 초록박스 : 첫번째를 4로 지정한다.
        second = temp; // 파란박스 : second값을 temp로 바꾼다.
    }

loop#4

 while (second) {
        const temp = second.next; // loop#3의 second의 next를 temp에 저장한다. (null이다.)
        second.next = first; // 빨간선 : 5의 pointer(next)를 4(loop#3의 초록박스)로 가리키게 한다.
        first = second; // 초록박스 : 첫번째를 5로 지정한다.
        second = temp; // 파란박스 : second값을 temp로 바꾼다.
    }

End loop

 while (second) {
   // second가 null이므로 loop가 끝났다.
    }

마지막으로 head = first로 바꾼다. (그림의 초록색 head 표시)

Summary

요약하면, 첫번째 pointer를 null으로 끊고, 3번째 pointer를 temp에 저장한다. 그리고 2번째 노드의 pointer를 첫번째로 옮긴다.

3번째 pointer를 temp에 저장해두는 이유는 2번째 노드 pointer를 변경하기 위해 저장해 두는 것이다.