206. Reverse Linked List

• python3

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Pseudocode

1. 두 개의 포인터를 정함.
   • prev = 앞
   • current = 현재
2. current가 나아가면 현재 노드가 가리키는 노드를 prev로 지정. 현재 노드는 prev가 되고 현재 노드가 원래 가리키던 노드로 이동.
3. 전부 이동하면 리스트가 거꾸로 뒤집어짐

Code

# 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 = None
        current = head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        return prev

Result

• Time Complexity : O(n)
• Space Complexity : O(1)