Title description:

Define a function that takes the head node of a linked list, reverses the list, and outputs the head node of the reversed list.

Example: input: 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: 5 – > 4 – > 3 – > 1 – > 2 – > NULL

Limit: 0 <= Number of nodes <= 5000

Solution 1: The three-pointer method

  1. Define three secondary Pointers. Cur represents the node that needs to be reversed and pre represents the previous node of cur. Iterate through the linked list
  2. Start by defining a temporary pointer to the temp record cur.next
  3. Set cur’s Next to pre and reverse
  4. Assign pre to the current cur
  5. Assign cur to the pre-reversed cur.next, which is the temp of the previous record (cannot be directly assigned to cur.next because it has already been reversed)

Time complexity: O(n)

Example code 1:

def reverseList(head: helper.ListNode) :
    pre, cur = None, head Step # 1

    while cur:
        temp = cur.next Step # 2
        cur.next = pre Step # 3
        pre = cur  Step # 4
        cur = temp Step # 5
    return pre
Copy the code

Problem 2: Recursion

  1. Pass in two Pointers, cur representing the current node, pre representing the previous node of the current node, and recurse
  2. If the current node cur is not empty, the recursion returns to its previous points
  3. Once you get the front node of the recursion, you reverse it

Time complexity: O(n)

Example code 2:

def reverseList(head: helper.ListNode) :
    def recursion(cur, pre) :  Step # 1
        if not cur: Step # 2
            return pre 
        res = recursion(cur.next, cur) Step # 3
        cur.next = pre
        return res

    return recursion(head, None)
Copy the code