07 | 链表（下）：如何轻松写出正确的链表代码？

作者：鲁米

2023-12-04
北京
本文字数：2099 字
阅读完需：约 7 分钟

今天我们讲到用哨兵来简化编码实现，你是否还能够想到其他场景，利用哨兵可以大大地简化编码难度？

哨兵是一种常见的编程技巧，可以在简化代码结构、边界处理等方面发挥重要作用。除了回文串判断中使用的哨兵外，还有一些其他场景可以利用哨兵来简化编码：

链表操作： 在链表中插入或删除节点时，可以使用哨兵简化边界处理。例如，在链表头部插入节点时，可以使用一个哨兵节点作为新的头节点，这样无论链表是否为空，都可以统一处理。
循环操作： 在某些循环中，通过引入哨兵元素，可以避免在每次迭代时都检查边界条件。这使得循环体内的逻辑更加简洁。
数组操作： 在处理数组时，哨兵可以用于简化边界检查。例如，在查找数组中的某个元素时，可以在数组末尾添加一个哨兵元素，以避免在循环中检查数组是否越界。
字符串处理： 在字符串处理中，哨兵可以用于标记字符串的开始或结束，使得在处理字符串时更容易处理边界情况。
树操作： 在二叉树等数据结构的操作中，哨兵节点可以用于处理边界情况，例如在遍历二叉树时，哨兵节点可以用于表示子树的末尾。
算法设计： 在一些算法中，通过引入哨兵元素，可以使算法更加简洁高效。例如，某些排序算法中引入哨兵可以减少对边界的判断。

哨兵的使用要根据具体的场景和问题来考虑，有时候它可以提高代码的可读性和性能。在编码时，可以通过合理使用哨兵来简化逻辑，减少边界条件的处理，使代码更加清晰和易维护。

1.链表操作中使用哨兵

class ListNode2 {    int val;    ListNode2 next;
    public ListNode2(int val) {        this.val = val;    }}
public class LinkedListWithSentinel {
    public ListNode2 insertAtHead(ListNode2 head, int value) {        ListNode2 sentinel = new ListNode2(0);        sentinel.next = head;
        ListNode2 newNode = new ListNode2(value);        newNode.next = sentinel.next;        sentinel.next = newNode;
        return sentinel.next;    }
    public static void main(String[] args) {                LinkedListWithSentinel list = new LinkedListWithSentinel();
        // 示例：在链表头部插入节点        ListNode2 head = new ListNode2(1);        head = list.insertAtHead(head, 2);        head = list.insertAtHead(head, 3);

        // 打印链表        while (head != null) {            System.out.print(head.val + " ");            head = head.next;        }    }}

复制代码

3.数组操作中使用哨兵

public class ArrayWithSentinel {
    public static int findElement(int[] arr, int target) {        int[] newArr = new int[arr.length + 1];        System.arraycopy(arr, 0, newArr, 0, arr.length);        newArr[arr.length] = target;  // 哨兵元素
        int index = 0;        while (newArr[index] != target) {            index++;        }
        return index == arr.length ? -1 : index;    }
    public static void main(String[] args) {        // 示例：查找数组中的元素        int[] array = {1, 2, 3, 4, 5};        int target = 3;
        int result = findElement(array, target);        System.out.println("Index of " + target + ": " + result);    }}

复制代码

5.二叉树操作中使用哨兵

package com.controller.bootweb.demo.dsa;
class TreeNode {    int val;    TreeNode left, right;
    public TreeNode(int val) {        this.val = val;        this.left = this.right = null;    }}
public class TreeWithSentinel {
    // 哨兵节点作为树的末尾    private static final TreeNode sentinel = new TreeNode(Integer.MAX_VALUE);
    // 在二叉搜索树中插入节点    public TreeNode insert(TreeNode root, int value) {        if (root == null) {            return new TreeNode(value);        }
        if (value < root.val) {            root.left = insert(root.left, value);        } else if (value > root.val) {            root.right = insert(root.right, value);        }
        return root;    }
    // 中序遍历打印树节点值    public void inorderTraversal(TreeNode root) {        if (root != null && root != sentinel) {            inorderTraversal(root.left);            System.out.print(root.val + " ");            inorderTraversal(root.right);        }    }
    public static void main(String[] args) {        TreeWithSentinel tree = new TreeWithSentinel();
        // 示例：插入节点并中序遍历        TreeNode root = null;        root = tree.insert(root, 5);        root = tree.insert(root, 3);        root = tree.insert(root, 7);        root = tree.insert(root, 2);        root = tree.insert(root, 4);
        // 中序遍历打印节点值        tree.inorderTraversal(root);    }}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/1466de7d8fa6c5b2aeaf530e7】。

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

07 | 链表（下）：如何轻松写出正确的链表代码？

1.链表操作中使用哨兵

3.数组操作中使用哨兵

5.二叉树操作中使用哨兵

鲁米

评论