0206-reverse-linked-list¶

Description¶

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?

Solution(Python)¶

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#   12345
#   dummy -> cur
#    while traversing list
#          prev-> current cur -> cur.next
#          prev <- cur <- cur.next
#          cur.next = previous
#          next_.next = cur
#          prev = cur
#          cur = cur.next
# simulation
#      1 2345
#      prev = 1
#      cur  = 2
#       -> 2
#           2.next = 1
#           3.next = 2
#           prev = 2
#           cur = 3
#         3
#           3.next = 2
#           4. next = 3
#           prev = 3
#           cur = 4
#         4
#           4.next = 3
#          5.next = 4
#          prev = 4
#          cur = 5
#  corrected
#   1 2 3 4 5 None
#    prev None
#    cur 
#    prev cur next
#      cur.next = prev
#      prev = cur
#      cur = next_
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        cur = head

        while cur:
            next_ = cur.next
            cur.next = prev
            prev = cur
            cur = next_

        return prev
        