•
문제 설명 : 제공된 연결리스트를 뒤집은 연결리스트 반환
•
풀이 방법
◦
개인적으로 푼 방법은, 1회 순회를 하면서 값을 얻어오고 해당 값을 사용하여 별도의 연결리스트를 새롭게 만든 방법이다.
•
시간복잡도 :
•
성공 코드
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
val_list = []
if head == None:
return head
while head != None:
val_list.append(head.val)
head = head.next
new_head = ListNode(val_list.pop())
cursor = new_head
while val_list:
cursor.next = ListNode(val_list.pop())
cursor = cursor.next
return new_head
Python
복사
•
성공 코드(Solution 참고)
현 노드와 현 노드의 다음 값을 백업하여 따로 연결하는 방식이다.
1회 순회만 진행되기 때문에 위 방식보다 최대 2배 빠르다.
솔루션의 코드의 변수명으로는 바로 파악이 어려웠는데, 막상 나눠보니 굉장히 간단한 방식이었다.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 새로운 커서와 이전 값을 저장할 prev 커서이다
curr = head
prev = None
while curr:
# 현 노드의 기존 다음 값 백업
nxt = curr.next
# 현 노드의 기존 next를 이전 값(prev)로 변경
# 첫 반복일 경우에는 초기 값 None이다.
curr.next = prev
# 다음 반복에 사용할 curr / prev를 각각 갱신
# prev는 현재 노드로
# curr은 다음 값으로
prev = curr
curr = nxt
return prev
Python
복사