Leetcode 206 Reverse Listnode

Problem description

Leetcode 206

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

Example:

• Input: [1,2,3,4,5]
• Output: [5,4,3,2,1]

Constraints:

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

Problem Solving Process

We first set the additional node = None, which will be used to update every node.

Temp is used to get the next node.

For every node we get in while loop, we let it to reverse connect to the last node.

In the first while loop:

head point to the node 1.

temp = head.next = 2   head.next = 1 -> = node = 1 -> None

node = head = 1   head = temp = 2

In the second while loop:

temp = head.next = 2.next = 3   head.next = 2-> = node = 2 -> (1 -> None)node

node = head = 2   head = temp = 3

…

The idea is connect the present node to node.

Code accomplish

class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        node = None
        while head:
            temp = head.next
            head.next = node
            node = head
            head = temp
        return node

Time complexity analysis

Because we need to connect every node, so the time complexity is:

O(n) (n is the length of List)

Space complexity analysis

In this question, we haven’t used extra data structure, so the space complexity will be:

O(1)