How to Realize Inverse Order of Chain List

Method 1: In-situ reverse sequence

Algorithmic idea: When traversing the list, modify the pointer field of the current node to point to its predecessor node. Therefore, a pointer is needed to save its precursor. In addition, in order to find the successor node after adjusting the pointer field of the current node, another pointer variable is needed to save the successor node. After all the nodes are saved, the reverse order can be completed directly.

Performance analysis of the algorithm:

This method traverses the linked list once, the time complexity is o(N), and the length of the linked list is N. However, a constant variable is needed to save the current node, the precursor node and the successor node, so the spatial complexity is o(1).

class LNode: def __init__(self, x): self.data = x self.next = None def Reverse(head): if head == None or head.next == None: return pre = None cur = None next = None cur = head.next next = cur.next cur.next = None pre = cur cur = next while cur.next != None: next = cur.next cur.next = pre pre = cur cur = next cur.next = pre head.next = cur if __name__ == "__main__": i = 1 head = LNode(i) head.next = None tmp = None cur = head while i<8: tmp = LNode(i) tmp.data = i cur.next = tmp cur = tmp i += 1 print("Before the reverse order:") cur = head.next while cur != None: print(cur.data) cur = cur.next print("After the reverse order:") Reverse(head) cur = head.next while cur!= None: print(cur.data) cur = cur.next

The results are as follows:

Before the reverse order: 1 2 3 4 5 6 7 After the reverse order: 7 6 5 4 3 2 1

Method 2: Insertion

Algorithmic idea: Set the first node of the list as the tail node, start from the second node of the list, insert one by one after the head node.

Performance analysis of the algorithm:

This method traverses the list once, so the time complexity is o(N), where N is the length of the list. The spatial complexity is o(1)

class LNode: def __init__(self, x): self.data = x self.next = None def reverse(head): if head is None or head.next is None: return cur = None next = None cur = head.next.next head.next.next = None while cur != None: next = cur.next cur.next = head.next head.next = cur cur = next if __name__ == "__main__": i = 1 head = LNode(i) head.next = None tmp = None cur = head while i<8: tmp = LNode(i) tmp.data = i cur.next = tmp cur = tmp i += 1 print("Before the reverse order:") cur = head.next while cur != None: print(cur.data) cur = cur.next print("After the reverse order:") reverse(head) cur = head.next while cur!= None: print(cur.data) cur = cur.next