Introduction of the list

Linked list is a common data structure, is a linear list. It does not store data in linear order, and it does not need to carve out contiguous storage space as opposed to arrays. Linked lists are suitable for scenarios with frequent insertion or deletion operations, and the time complexity is O(1). However, since elements cannot be accessed by subscript, the query efficiency is low and the time complexity is O(n). The nodes of a linked list have a property to store data, called val in this article, and a next pointer to the next node, so that nodes are joined one by one to form the list. The main types of linked lists are single linked list, bidirectional linked list, circular linked list. For more information, see Wikipedia-linked list.

Singly linked lists

A single linked list is shown in the following figure:

A singly linked list is also called a unidirectional list. As the name implies, it has only one direction, that is, a next pointer to the next node. Now that we know how single-linked lists behave, we can start writing code to create single-linked lists.

Single linked list node structure:

class ListNode {
    constructor(val) {
    	// Save data
        this.val = val
        // Used to point to the next node
        this.next = null}}Copy the code

Create a single linked list and add and delete elements:

class LinkedList {
    constructor(val) {
        this.head = new ListNode(val)
        this.size = 1
    }

    append(val) {
        if (!this.head) {
            this.head = new ListNode(val)
            return
        }

        const newNode = new ListNode(val)
        let p = this.head

        while (p.next) {
            p = p.next
        }

        p.next = newNode
        this.size++
    }

    deleteByVal(val) {
        // Virtual head node, easy to delete head node
        const dummyHead = new ListNode(0)
        dummyHead.next = this.head
        let p = dummyHead

        while(p.next && p.next.val ! == val) { p = p.next }// This object does not exist, return -1
        if(! p.next) {return -1
        }

        p.next = p.next.next
        this.head = dummyHead.next
        this.size--
    }

    deleteByIndex(index) {
        if (index > this.size || index <= 0) {
            return -1
        }

        const dummyHead = new ListNode(0)
        dummyHead.next = this.head
        let p = dummyHead, i = 1

        while(p.next && i ! == index) { p = p.next i++ } p.next = p.next.nextthis.head = dummyHead.next
        this.size--
    }

    traversal() {
        const res = []
        let p = this.head

        while (p) {
            res.push(p.val)
            p = p.next
        }

        console.log(res)
    }
}


const linkedList = new LinkedList(0)
linkedList.traversal() / / [0]
linkedList.append(1)
linkedList.append(2)
linkedList.append(3)
linkedList.traversal() // [0, 1, 2, 3]
linkedList.deleteByVal(3)
linkedList.traversal() / / [0, 1, 2]
linkedList.deleteByVal(0)
linkedList.traversal() / / [1, 2]
console.log(linkedList.deleteByVal(0)) // -1
linkedList.deleteByIndex(1)
linkedList.traversal() / / [2]
linkedList.deleteByIndex(1)
linkedList.traversal() / / []
console.log(linkedList.deleteByIndex(1)) // -1
Copy the code

Here the main implementation of add, delete, traversal method; Adding an element to an index or adding a value is similar to deleting a node. Notice that I used dummyHead here, which is a technique that makes it very convenient to handle the head node. And we’re going to use this technique in future examples.

Two-way linked list

Bidirectional lists have more prev Pointers than single lists to point to the previous node.

Here is a bidirectional list node structure definition code:

class DLinkedNode {
    constructor(val) {
        this.prev = null
        this.next = null
        this.val = val
    }
}
Copy the code

For the creation of bidirectional linked lists and the implementation of the method of adding elements, we can use virtual head nodes and virtual tail nodes to facilitate subsequent operations.

class DLinkedList {
    constructor() {
        this.dummyHead = new DLinkedListNode('head')
        this.dummyTail = new DLinkedListNode('tail')
        this.dummyHead.next = this.dummyTail
        this.dummyTail.prev = this.dummyHead
    }

    append(val) {
        const newNode = new DLinkedListNode(val)

        newNode.next = this.dummyTail
        newNode.prev = this.dummyTail.prev
        this.dummyTail.prev.next = newNode
        this.dummyTail.prev = newNode
    }

    traversal() {
        let p = this.dummyHead.next
        const res = []

        while (p && p.next) {
            res.push(p.val)
            p = p.next
        }

        console.log(res)
    }
}

const dLinkedList = new DLinkedList()
dLinkedList.append(1)
dLinkedList.append(2)
dLinkedList.append(3)
dLinkedList.append(4)
dLinkedList.append(5)
dLinkedList.traversal() // [1, 2, 3, 4, 5]
Copy the code

With the virtual tail node here, it’s easy to add elements by simply manipulating the tail node.

Circular linked list

A circular list is one where the last node points to the head node, but I won’t go into that too much here.

Let’s look at a few topics:

sample

2. Add two numbers

206. Reverse linked lists

141. Circular linked lists

The sum of two Numbers

var addTwoNumbers = function(l1, l2) {
    // dummyHead virtual head node, used to hold the merged linked list
    const dummyHead = new ListNode(0)
    // A pointer to the current process, each time a new node is constructed through curr.next
    let curr = dummyHead, carry = 0

    while (l1 || l2 || carry > 0) {
        const val1 = l1 ? l1.val : 0
        const val2 = l2 ? l2.val : 0
        const sum = val1 + val2 + carry

        curr.next = new ListNode(sum % 10)
        carry = Math.floor(sum / 10)

        l1 = l1 && l1.next
        l2 = l2 && l2.next
        curr = curr.next
    }

    return dummyHead.next
};
Copy the code

In fact, there are many similar operations, such as string addition, which is the addition of large numbers. Do it if you’re interested. Here is mainly related to the linked list pointer processing.

Reverse a linked list

We can use double Pointers, prev for the previous node, curr for the current node; Then set curr.next to prev each time; With this loop, the linked list is reversed. The specific code is as follows:

var reverseList = function(head) {
    let prev = null, curr = head

    while (curr) {
    	// We need to save curr.next, otherwise we can't proceed to the next operation
        const next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    }

    return prev
};
Copy the code

Circular linked list

We could use Set to solve this problem, but there’s a more interesting way to do it: the fast pointer takes two steps at a time, the slow pointer takes one step at a time, and if there’s a loop, the fast pointer will catch up with the slow pointer. The concrete implementation is as follows:

var hasCycle = function(head) {
    let fast = head, slow = head

    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next

        if (fast === slow) {
            return true}}return false
};
Copy the code

Summary: Linked list operations actually change the pointer around, we need to pay attention to some boundary issues. At the same time, pay attention to the use of virtual nodes, fast and slow Pointers and other skills to optimize the code.

Leetcode antithesis making address: https://github.com/webpig/leetcode, after will continue to organize more antithesis. Welcome to communicate with us.