算法通关存第一关------链表青铜挑战笔记-Toy模板网

这篇具有很好参考价值的文章主要介绍了算法通关存第一关------链表青铜挑战笔记。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、如何构造链表

public class Node {
    public int var;
    public Node next;
}

如上代码其实就已经构造出了一个链表。

定义一个Node结点类，他有两个属性var，和next。由于next是Node类型，这时候next又会指向同为Node类型的对象，这个对象也拥有var，和next两个属性，由此构造出一个链表。

文章最后会有构造链表实例，完整代码。

二、链表的插入、删除

2.1 插入结点

在插入链表之前，先判断链表是否为空、位置参数是否合法。

//单链表插入
    public static Node insertNode(Node head, Node nodeInsert, int position) {
        //判断链表是否为空
        if (head == null) {//头结点为空，可以直接返回插入节点，也可以直接抛出异常
            return nodeInsert;
        }
        //判断位置参数是否合法
        int size = getLinkedListLength(head);
        if (position < 1 || position > size + 1) {
            System.out.println("位置参数越界了");
            return head;
        }
        return head;
    }

链表插入结点，可以分为头部插入和中部插入（尾部插入算法与之类似）。

public static Node insertNode(Node head, Node nodeInsert, int position) {
        //在链表头部插入结点
        if (position == 1) {
            nodeInsert.next = head;
            head = nodeInsert;
            return head;
        }
        //在链表中部或尾部添加结点
        //实现思路：先找到目标位置前一个结点，先将新增结点的next指向目标结点，然后将目标结点的next指向新增结点
        Node pNode = head;
        int count = 1;
        while (count < position - 1) {
            pNode = pNode.next;
            count++;
        }
        nodeInsert.next = pNode.next;
        pNode.next = nodeInsert;
        return head;
    }

注意：在插入结点时，应先将插入结点的next指向目标节点，然后将目标节点的前一个节点（pNode）的next指向插入节点。

考虑：为什么这两步为什么不能颠倒？

2.2 删除结点

在链表删除时，也要考虑链表是否为空链，参数是否合法，具体代码见 2.1 图一。

删除头部节点只需要将head指向head.next。

删除非头部节点的思想是，找到目标节点的前一个结点preNode，将preNode.next指向目标节点的next（即preNode.next.next=preNode）。

如下代码是将preNode.next指向目标节点curNode，然后将preNode.next指向curNode.next,由此把cerNode架空，被jvm收走。以上两种方法都可行。

//单链表删除节点
    public static Node deleteNode(Node head, int position) {
        //删除头结点
        if (position == 1) {
            head = head.next;
            return head;
        } else {
            //若不是头结点，则  
            // 先找到目标节点的前一个节点preNode，然后将preNode的next指向目标结点的next
            Node preNode = head;
            int count = 1;
            while (count < position - 1) {
                preNode = preNode.next;
                count++;
            }
            Node curNode = preNode.next;
            preNode.next = curNode.next;
            return head;
        }
    }

实例

将给定数组转化为链表文章来源地址https://www.toymoban.com/news/detail-612577.html

public class BasicLink {
    public static void main(String[] args) {
        //给定数组，将其转化为链表
        int[] a = {1, 2, 3, 4, 5, 6};
        //调用自定义的静态初始化方法，将数组a传入参数
        Node head = initLinkedList(a);
        System.out.println(head);
    }
    //自定义链表 的 静态初始化方法
    private static Node initLinkedList(int[] array) {
        Node head = null, cur = null;
        for (int i = 0; i < array.length; i++) {
            //通过创建内部类对象，调用内部类的构造方法，并将数组中的元素赋值给结点的var属性
            Node newNode = new Node(array[i]);
            newNode.next = null;
            if (i == 0) {
                head = newNode;
                cur = newNode;
            } else {
                cur.next = newNode;
                cur = newNode;
            }
        }
        return head;
    }
    //内部类
    static class Node {
        public int var;
        public Node next;
        //构造方法，创建节点对象，并将参数x复制给var
        Node(int x) {
            var = x;
            next = null;
        }
    }

}

到了这里，关于算法通关存第一关------链表青铜挑战笔记的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！