Subject to introduce

Buckle 707: leetcode-cn.com/problems/de…

Method: one-way linked list

According to the requirements of the topic, it is necessary to realize the function of adding, deleting, changing and checking the linked list, so we need to define our own data structure to realize the function, it is easy to think of using the single linked list data structure, the structure is simply defined as follows:

class ListNode {
    int val;/ / the node values
    ListNode next;// Pointer to the next node
    public ListNode(int val) {
        this.val = val; }}Copy the code

Next refers to the head node of the single list. We also need to use the variable size to record the number of nodes in the current list. When adding a node, size++ is used. Perform the size -.

The code is as follows:

class MyLinkedList {

    class ListNode {
        int val;/ / the node values
        ListNode next;// Pointer to the next node
        public ListNode(int val) {
            this.val = val; }}// The first node on the list
    ListNode dumy = null;

    int size = 0;// Number of nodes

    public MyLinkedList(a) {
        dumy = new ListNode(-1);// Initialize the dummy node
        dumy.next = null;
    }

    public int get(int index) {
        if(index < 0 || index >= size) {
            return -1;
        }
        ListNode temp = dumy.next;
        for(int i = 0 ; i < index; i++) {
            temp = temp.next;
        }
        return temp.val;
    }

    /** * Add node */ to the list header
    public void addAtHead(int val) {
        ListNode newHead = new ListNode(val);
        newHead.next = dumy.next;
        dumy.next = newHead;
        size++;
    }

    /** * the element at the end of the list */
    public void addAtTail(int val) {
        ListNode temp = dumy;
        while(temp.next ! =null) {
            temp = temp.next;
        }
        ListNode tailNode = new ListNode(val);
        temp.next = tailNode;
        size++;
    }

    /** * To add an element to the specified index, you also need to find the last node of the index */
    public void addAtIndex(int index, int val) {
        if(index > size) {
            return;
        }else if(index == size) {
            // Insert nodes at the end
            addAtTail(val);
        }else if(index <= 0) {
            // Insert nodes at the head of the list
            addAtHead(val);
        }else {
            // Insert a common node
            ListNode temp = dumy;
            for(int i = 0; i < index ; i++) {
                temp = temp.next;
            }
            ListNode insertNode = newListNode(val); insertNode.next = temp.next; temp.next = insertNode; size++; }}/** * To delete the node with the specified index, you need to find the last node of the corresponding node of the index */
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size) {
            return;
        }
        ListNode temp = dumy;
        for(int i = 0; i < index; i++) { temp = temp.next; } temp.next = temp.next.next; size--; }}Copy the code

Complexity analysis

• Time complexity: O(N), where N is the number of nodes in the linked list
• Space complexity: O(1)