문제 요약
자세한 내용은 leetcode에서 확인
https://leetcode.com/problems/reverse-linked-list/
Singly Linked List (단방향) 을 반대로 뒤집어라.
예제
input: 1 -> 2 -> 3 -> NULL
output: 3 -> 2 -> 1 -> NULL
풀이
3 포인터 개념으로 풀 수 있다.
간단하게 요약하면
1. 전, 지금, 다음 포인터를 만든다
2. 지금 노드의 다음은 전 포인터를 가리킨다
3. 전 포인터는 지금 포인터를 가리킨다
4. 지금 노드는 다음 포인터를 가리킨다
public ListNode reverseList(ListNode head) {
ListNode curr = head;
// 마지막 노드는 null을 가리키기 때문에 null부터 시작한다
ListNode prev = null;
// curr이 null이라면 리스트의 마지막에 다다랐다는 소리
while (curr != null) {
// curr.next를 저장해둔다
ListNode next = curr.next;
// 지금 노드의 다음은 전 포인터를 가리킨다
curr.next = prev;
// 전 포인터는 지금 포인터를 가리킨다
prev = curr;
// 지금 포인터는 다음 포인터를 가리킨다
curr = next;
}
// prev 포인터가 새로운 head 노드가 된다
return prev;
}
Complexity
time: O(n) - n 노드 갯수 만큼 while loop을 돈다.
space: O(1) - 몇개 안되는 변수를 생성하였다.