leetcode 206. Inversion Link List

• Title:
  Reverse a single linked list.
• Examples:

Input: 1 - > 2 - > 3 - > 4 - > 5 - > NULL
 Output: 5 - > 4 - > 3 - > 2 - > 1 - > NULL

• Advancement:
  You can reverse the list iteratively or recursively. Can you solve this problem in two ways?
• Code 1:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head
        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node
        head = prev
        return head
# Execution time: 52 ms, beating 83.84% of all Python 3 submissions
# Memory consumption: 14.8 MB, beating 19.68% of all Python 3 submissions

• Algorithmic description:
  Set two pointers, prev for null pointer, current for current header node. Set up a loop. When current points to the last node, the value is Null. The loop ends. In the loop, next_node is used to store the next node of the current node. Then the current node and the next node are exchanged to move the pointer of the current node to the next node. Next, continue the cycle.
  The first cycle:
  (1) Step 1: next_node = current.next
  The current.next is assigned to the next_node variable. Next points to node 2 and saves node 2 first.
  
  (2) Step 2: current.next = prev
  Assign prev = None to current.next, which means that node 1 points to Null.
  
  (3) Step 3: prev = current
  The current is assigned to prev, which points to node 1.
  
  (4) Step 4: current = next_node
  Assign next_node to current, that is, current points to node 2. Set node 2 as "head node".
  
  Second cycle:
  (1) Step 1: next_node = current.next
  The current.next is assigned to the next_node variable. Next points to node 3 and saves node 3 first.
  
  (2) Step 2: current.next = prev
  The prev = None is assigned to current.next. In the first cycle, prev points to node 1, and in the second cycle, node 2 points to node 1, which completes the flip.
  
  (3) Step 3: prev = current
  The current is assigned to prev, which points to node 2.
  
  (4) Step 4: current = next_node
  Assign next_node to current, that is, current points to node 3. Set node 3 as "head node".
  
  Continuous cycle to complete all node flip:
  
  The complete process is as follows:
  
• Code 2:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None:
            return head
        a =[]
        result = ListNode(None)
        while head != None:
            a.append(head.val)
            head = head.next
        a = a[::-1]
        for i in range(len(a)):
            node = ListNode(a[i])
            if i == 0:
                temp = node
            result.next = node
            result = result.next
        return temp
# Execution time: 92 ms, beating 7.91% of all Python 3 submissions
# Memory consumption: 15.9 MB, beating 14.51% of all Python 3 submissions

• Algorithmic description:
  Create a list a and a list result; traverse and store the elements in the head list into list a, first flip the list a, then add the elements in a to the list result one by one. Note that when first added, save the header node temp = node, and then return to the header node temp.

• Code 3:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None:
            return head
        result = ListNode(head.val)
        head = head.next
        while head != None:
            result = self.insert(0,head.val,result)
            head = head.next
        return result
    def insert(self,key,value,result): #lian biao cha ru yuan su
        node = ListNode(value)
        node.next = result
        return node
# Execution time: 60 ms, beating 47.19% of all Python 3 submissions
# Memory consumption: 15.7 MB, beating 14.51% of all Python 3 submissions

• Algorithmic description:
  First determine whether the list is empty, if it is empty, return directly; establish an empty list result, let the head of the list result point to the head, and then move the head pointer backward one bit, that is head = head.next; establish a loop when the head is not empty, use insert function, insert the elements of the head list one by one. Go to the head of the new list result and return to result.