[Linked List] Reverse Linked List

Reverse a singly linked list.

간단하게 Linked List가 존재할 때 얘를 reverse 하라는 문제

그러나 절대 간단하지 않다. 1시간걸린듯 ㅠㅠ 

 

Linked List는 항상 head와 tail을 생각해보자

하나의 Linked List 원소는 head라고 하고, head는 항상 다음 원소, 즉 tail 노드를 가리키고 있다.

코테에서 Input의 형태는 간단히 Array로 표현되지만,

기본적으로 head 노드가 들어오고 그것의 next메소드가 tail노드를 가리키게 되어있다

 

시간이 꽤나 오래걸렸는데, 쉽게 설명되지 않으니 자필 다이어그램을 준비했다.

1) [ 1, 2, 3, 4, 5] 인풋은 사실 1->2->3->4->5와 같다.

이때 가장 첫 head노드인 1이 input으로 들어오고, 얘는 tail노드가 2라는 사실을 알고 있다.

 

2) 일단 current라는 변수에 head노드인 1을 담는다.

basic Linked List는 previous 노드를 알 수 없으므로, previous 변수를 설정하고 null을 할당한다

 

<여기부터 Loop>

 

3) 여기서 index를 하나 만드는데, 이는 다음 조작대상이 되는 노드를 설정하기 위해서다.

우리가 로직을 통해 head노드가 가리키는 tail노드를 반대로 바꿔버리면 원래의 tail노드는 알 수가 없다. 

따라서 로직 적용 전 시점에서 tail노드를 index에 담아 기억하는 것이다.

 

4) current(head 노드)가 가리키던 tail노드를 2가 아닌 previous 노드로 바꾼다: 1->2 가 1->null이 된다.

 

5) current노드는 reverse가 완료되었으므로 previous 에 담는다 

 

6) 그리고 2를 꺼내 다음 reverse 로직 처리의 current로 지정한다.

 

7) 2역시 4번 로직을 통과하면 2->3에서 2->1로 변경될 것이다. 물론 이때의 index는 3이었을것이므로 다음 Loop에서는 3에 대한 로직처리가 진행된다.

 

8) 끝까지 처리가 되면 current가 없을것이고 Loop문이 종료된다. 마지막 원소를 리턴하면 된다.