Reverse Linked List

나의 논리

링크드 리스트에 대한 개념은 있었는데 이 개념을 어떻게 구현으로 옮길 줄 몰랐다. 이 부분은 부끄럽게 생각한다.

재귀를 사용하여 이 문제를 풀려고 했다.
Node.next가 None인게 마지막 노드이므로 이 노드를 첫 노드로 삼고 리턴하면 이전 노드의 호출스택으로 온다.
그럼 현재 호출 스택에서는 상위 호출스택에서 넘어온 노드
,예를 들면 node.next = None인 노드 (문제의 첫번째 예시에서는 5),와 현재 호출스택의 노드 node.next = 5, node.val = 4인 현재의 노드가 있다.

난 이부분을 어떻게 해결해야 할 지 몰라서 답을 보고 말았다.

정답코드

node,prev = head , None

while node:
	next,node.next= node.next,prev
	prev , node = node, next
    
return prev

1->2->3->4->5
라는 링크드 리스트가 있다고 치자

처음에 좀 많이 햇갈렸는데 찬찬히 살펴보면
next 노드를 현재의 다음 노드 node.next로 초기화 한다.
현재의 node가 1이라면 node.next는 2이므로 next는 2인 노드가 된다.

현재의 1인 노드의 node.next를 prev로 바꿔준다.
즉 1다음에 None이 오도록 한다. 그럼 node는
1->None 형태이다.

그 다음 라인에서
prev를 1->None으로 바꿔주고 node를 2로 옮긴다.

그 다음 반복에서는
node.next 즉 2.next는 3이므로 next는 3이 되고
현재 2.next에 prev를 대입, 즉 2->1->None이 된다.

이런식으로 node가 None일때까지 진행하고 prev를 리턴하면 5->4->3->2>->1로 링크드 리스트를 뒤집을 수 있다.