白话数据结构与算法------链表

class Node:
    data = 0
    next = None

def build_single_link_list(nodeArr):
    headNode = None #头结点
    nextNode = None #尾节点
    for i in nodeArr:
        node = Node()
        node.data = i
        node.next = None
        if headNode is None:
            headNode = node
            nextNode = headNode
        else:
            nextNode.next = node
            nextNode = node
    return headNode

# 打印链表
def printLinkList(head):
    while head is not None:
        print(head.data)
        head = head.next

# 在O(1)时间删除链表节点
# 分析：用下一个节点数据覆盖要删除的节点
def deleteRandomNode(cur):
    if cur is None:
        return
    pNext = cur.next
    cur.data = pNext.data
    cur.next = pNext.next
    del pNext

# 链表反转1
def reverse1(head):
    if head is None or head.next is None:  #判断当前链表是否为空或者只有一个节点
        return head
    current = head
    pre = None
    pnext = None
    while current is not None:
        pnext = current.next  #1.存起来下一个节点
        current.next = pre #2.将当前节点指向上一个节点(第一次指向None)
        pre = current #3.将头指针指向当前节点
        current = pnext #4.将当前节点指向下一个节点，用以下一次逆转
    return pre

#链表反转2
def reverse2(current):
    if current.next is None:
        return current
    pnext = current.next #先取出下一个节点
    current.next = None #将当前节点的下一个节点指向空
    reversed = reverse2(pnext) #将下一个节点传入执行相同操作
    pnext.next = current #将下一个节点指向当前节点
    return reversed #依次递归直到链表最后节点成为当前节点

if __name__ == '__main__':
    head = build_single_link_list([1, 2, 3, 4, 5, 6])
    head = reverse2(head)
    deleteRandomNode(head.next.next)
    print("第一次反转链表:")
    while head is not None:
        print(head.data)
        head = head.next

未完待续...