python链表 —— 有头结点和没有头结点的区别

不论是带头结点的链表还是不带头结点的链表，头指针head都指向链表中的第一个结点。如果该链表有头结点，则头指针head指向头结点，如果没有头结点，则头指针head指向链表的第一个节点。

1 带头结点的单链表中头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储信息。头指针head始终不等于NULL，head->next等于NULL的时候链表为空。

2 不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL的时候链表为空。

头结点的存在，使得空链表与非空链表的处理变得一直，也方便了对链表的开始结点插入或删除操作。

不带头结点的实现如下：

class ListNode:
    def __init__(self, value=None, next=None):
        self.data = value
        self.next = next
 
 
def creat_List(l, n):
    l.data = int(input())
    p = l
    for i in range(n-1):
        node = ListNode()
        node.data = int(input())
        p.next = node
        p = p.next
    
    p.next = None
    
def length(l):
    p = l
    len = 0
    while p:
        len += 1
        p = p.next
    return len
 
# 链表逆转
def reverse(l):
    res = pre = None
    p = l
    while p:
        pre = p.next
        p.next = res
        res = p
        p = pre
    return res 
 
def traverse(l):
    p = l
    while p:
        print(p.data, ' ', end='')
        p = p.next
    
    print()
 
if __name__ == '__main__':
    l = ListNode()
    creat_List(l, 5)
    traverse(l)
    ll = reverse(l)
    traverse(ll)
    traverse(l)