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


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

 

Posted on Sat, 12 Oct 2019 14:50:45 -0700 by chalbing