02链表的逆序

• • 题目描述（难度：中等）
  • 单链表结构
  • 方法一
  • • 复杂度分析
  • 方法二：插入法
  • • 复杂度分析
  • 主函数
  • 参考文献

给定一个带头结点的单链表，请将其逆序。即如果单链表原来为head->1->2->3->4->5->6->7，那么逆序后变为head->7->6->5->4->3->2->1。

class LNode:
    def __init__(self):
        self.data = None # 数据域
        self.next = None # 指针域

• 由于单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。
• 注意：在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。

以head->1->2->3->4为例，如下图。

# 单链表进行逆序 
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
  # 使当前遍历到的结点cur指向其前驱结点
    while cur.next != None:
        next = cur.next
        cur.next = pre
        pre = cur
        # cur = cur.next
        cur = next
    # 链表最后一个结点指向倒数第二个结点
    cur.next = pre
  # 链表的头结点指向原来链表的尾结点
    head.next = cur

• 时间复杂度为 O ( n ) O(n) O(n)
• 空间复杂度为 O ( 1 ) O(1) O(1)

#插入法
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 is not  None:
           next = cur.next
           cur.next = head.next
           head.next = cur
           cur = next

• 时间复杂度为 O ( n ) O(n) O(n)
• 空间复杂度为 O ( 1 ) O(1) O(1)

if __name__ == "__main__":
    i = 1
  # 链表头结点
    head = LNode()
    cur = head
  # 构造单链表
    for i in range(1,8):
        tmp = LNode()
        tmp.data = i
        cur.next = tmp
        cur = tmp
        i += 1
    print('逆序前：', end='')
    cur = head.next
    while cur != None:
        print(cur.data, '', end='')
        cur = cur.next
    print('n逆序后：', end='')
    Reverse(head) # 对链表进行逆序
    cur = head.next
    while cur != None:
        print(cur.data, '', end='')
        cur = cur.next

[1] 何海涛. 剑指Offer：名企面试官精讲典型编程题（第2版）. 北京： 电子工业出版社，2017
[2] 张波，楚秦. Python程序员面试算法宝典. 北京：机械工业出版社，2018