LeetCode 206번 - Reverse Linked List

문제

주어진 연결 리스트를 역순으로 만드는 문제이다.

---

살펴보기

이 문제는 아주 유명하면서 중요한 문제라고 한다.

 

간단하게 후입선출법인 스택을 이용해 노드를 저장했다가 다시 꺼내는 방식으로 뒤집을 수 있지만,

이 방법보다는 포인터를 이용해 노드를 뒤집는 방법이 더 적절하다고 한다.

 

포인터를 이용한 방법에서는 총 3개의 준비물이 필요하다.

 

주어진 노드, 노드를 순회할 포인터, 역순을 저장할 노드

 

주어진 노드 head와, head의 현재 노드를 가리킬 temp, 뒤집을 노드를 저장할 노드 reverse를 이용해서 문제를 풀었다.

 

ListNode인 temp를 생성해 head를 가리킨다.

head는 다음 칸으로 한 칸 이동시킨다.

temp의 다음 노드를 reverse와 연결한다.

마지막으로 reverse를 temp와 연결시켰다.(기존 연결리스트와는 연결이 끊어지게 된다..)

 

이번 문제는 이해를 잘 해보려고 표를 그려가면서 풀었다..

 

 

첫 번째 반복문

 

두 번째 반복문

 

세 번째 반복문

 

아마 이런 식으로 연결 리스트가 뒤집히는 것 같다..

 

int, String 등 단순 구조의 값을 스왑할 때와 비슷한 원리같은데, 연결 리스트에서는 한 단계가 추가되다 보니 처음 보는 입장에서 어려웠다..

---

풀어보기

if(head==null) return null;

ListNode prev = null;

while(head!=null){
    ListNode curr = head;
    head = head.next;
    curr.next = prev;
    prev = curr;
}

return prev;

 

+ 스택을 사용한 방법

Stack<ListNode> stack = new Stack<>();

while(head!=null){
    stack.push(head);
    head = head.next;
}

head = stack.pop();
ListNode reverse = head;

while(!stack.isEmpty()){
    reverse.next = stack.pop();
    reverse = reverse.next;
}
reverse.next = null;

return head;