单链表之头插法和尾插法

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。指针域指向下一个节点，最后一个节点的指针域指向空。头插法和尾插法是单链表常用的两种插入方法，下面我们将通过动图和图解的方式，详细介绍这两种插入方法。

一、头插法

头插法是指在单链表的头部插入新的节点。具体步骤如下：

1. 创建一个新的节点，并将数据域赋值为需要插入的值。
2. 将新节点的指针域指向原链表的头部节点。
3. 将原链表的头部指针指向新节点。

通过以上步骤，新节点就被插入到了单链表的头部。

下面是一个简单的示例代码，演示如何使用头插法在单链表中插入一个新节点：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def insert_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node

在这个示例中，我们定义了一个ListNode类来表示单链表中的节点，其中val表示节点的值，next表示指向下一个节点的指针。insert_at_head函数用于在单链表的头部插入一个新的节点，它首先创建一个新的节点，然后将新节点的next指针指向原链表的头部节点，最后返回新节点作为新的头部节点。

二、尾插法

尾插法是指在单链表的尾部插入新的节点。具体步骤如下：

1. 创建一个新的节点，并将数据域赋值为需要插入的值。
2. 遍历原链表，找到最后一个节点。
3. 将最后一个节点的指针域指向新节点。
4. 将新节点的指针域指向空。

通过以上步骤，新节点就被插入到了单链表的尾部。

下面是一个简单的示例代码，演示如何使用尾插法在单链表中插入一个新节点：

def insert_at_tail(head, val):
    if not head:
        return ListNode(val)
    curr = head
    while curr.next:
        curr = curr.next
    curr.next = ListNode(val)
    return head

在这个示例中，我们定义了一个ListNode类来表示单链表中的节点，其中val表示节点的值，next表示指向下一个节点的指针。insert_at_tail函数用于在单链表的尾部插入一个新的节点，它首先判断原链表是否为空，如果为空则直接创建一个新节点作为头部节点并返回；否则遍历原链表，找到最后一个节点，并将最后一个节点的next指针指向新节点，最后返回头部节点。