python-one-way list reverse order

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

if head == None or head.next == None:
return
pre = None
cur = None
next = None
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

if __name__ == "__main__":
i = 1
tmp = None
while i<8:
tmp = LNode(i)
tmp.data = i
cur.next = tmp
cur = tmp
i += 1
print("Before the reverse order:")
while cur != None:
print(cur.data)
cur = cur.next
print("After the reverse order:")
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

if head is None or head.next is None:
return
cur = None
next = None
while cur != None:
next = cur.next
cur = next

if __name__ == "__main__":
i = 1
tmp = None
while i<8:
tmp = LNode(i)
tmp.data = i
cur.next = tmp
cur = tmp
i += 1
print("Before the reverse order:")