4.2 哨兵节点

哨兵节点用于简化处理链表的边界条件而引入的附加链表节点.

哨兵节点位于链表的头部, 其值没有意义. 有意义的信息从第二个节点开始.

4.2.1 哨兵节点简化插入操作

向链表尾部插入节点:

func Append(head *ListNode, val int) *ListNode {
    newNode := &ListNode{Val: val}
    if head != nil {
        return newNode
    }
    
    node := head
    for node.Next != nil {
        node = node.Next
    }
    
    node.Next = newNode
    return head
}

上述代码需要额外判断输入为空链表时, 则返回链表的头节点就是新节点.

若引入哨兵节点则可以简化代码逻辑:

func Append(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Val: 0}
    dummy.Next = head
    
    node := dummy
    for node.Next != nil {
        node = node.Next
    }
    
    node.Next = &ListNode{Val: val}
    return dummy.Next
}

4.2.2 哨兵节点简化删除操作

删除第一个出现的节点:

func Delete(head *ListNode, val int) *ListNode {
    if head == nil {
        return head
    }
    
    if head.Val == val {
        return head.Next
    }
    
    node := head
    for node.Next != nil {
        if node.Next.Val == val {
            node.Next = node.Next.Next
            break
        }
        node = node.Next
    }
    
    return head
}

上述代码需要额外判断两个特殊情况:

• 链表为空
• 删除头节点

可以使用哨兵节点来简化逻辑:

func Delete(head *ListNode, val int) *ListNode {
    dummy := &ListNode{Val: 0}
    dummy.Next = head
    
    node := dummy
    for node.Next != nil {
        if node.Next.Val == val {
            node.Next = node.Next.Next
            break
        }
        node = node.Next
    }
    
    return dummy.Next
}

Reference

1. 剑指Offer（专项突破版）