문제15: 역순 연결리스트

문제

입력

1->2->3->4->5->NULL

출력

5->4->3->2->1->NULL

풀이

1. O(n) 풀이
1. 반복 한번으로 역순을 만든다.

if head == None: return None
result = copy.copy(head)
result.next = None
head = head.next
while head:
    temp = copy.copy(head)
    temp.next = result
    result = temp
    head = head.next

return result

1. 재귀를 활용한 풀이
1. 헤드값만 리턴하면 되므로,

def reverse(node: ListNode, prev: ListNode = None):
	if not node:
		return prev
	next, node.next = node.next, prev
	return reverse(next, node)

return reverse(head)

1. 반복을 활용한 풀이

node, prev = head, None

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

return prev

새로운 개념