1, the linked list

  • Dynamic arrays have the obvious disadvantage of wasting memory space
  • So as much memory as we want to use, we can use linked lists
  • Linked list: a linear list of linked storage. The memory addresses of all elements are not necessarily contiguous
  • Linked list stores create a node containing (element, pointer to next node next)
  • A linked list has a head node and a tail node, with the tail node pointing to NULL at the end

2. Design of linked lists

  • The class that creates LinkedList manages the LinkedList data, size manages the memory size of the LinkedList, and first points to the next node

  • The node node contains the element Element, and next points to the next node

    public class LinkedList { private int size; private Node first; Private class Node {E element; Node next; Public Node(E element, Node next) {this.element = element; this.next = next; }}}

3. Interface design

3.1. Interface design list

/** * clear all elements */ void clear(); /** * the number of elements */ int size(); /** * Contains an element * @param Element * @return */ Boolean contains(E element); * @param index * @return */ E get(int index); ֵ */ E set(int index, E element); /** * set(int index, E element); /** * insert an element * @param index * @param element */ void add(int index, E element); * @param index * @return */ E remove(int index); * @param element * @return */ int indexOf(E element);Copy the code

3.2, clear element clear ()

Public void clear() {size = 0; // first = null; // address to null}Copy the code
  • Clear the size, first address to null

3.3, number of elements

public int size() {
    return size;
}
Copy the code
  • Return the number of sizes

3.4, whether to contain elements

//ELEMENT_ON_FOUND = -1 public boolean contains(E element) { return indexOf(element) ! = ELEMENT_ON_FOUND; }Copy the code
  • Call the query function directly to see if it exists

3.5, get the element at index position

Public E get(int index) {return node(index).element; }Copy the code
  • Fetch the corresponding element in Node according to the following table

3.6, modify the index element

Public E set(int index, E element) {public E set(int index, E element) {node <E> node = node(index); E old = node.element; // Overwrite element node.element = element; // Return old; }Copy the code

3.7, add an element to the corresponding index

Public void add(int index, E element) {// Check whether the index is out of bounds rangeCheckForSize(index); First = new Node<E>(element, first.next); // If (index == 0) {first = new Node<E>(element, first.next); }else {// find Node<E> prev = Node (index-1); Next = new Node<>(element, prev.next); } size++; }Copy the code
  • To add an element to the index, simply create a new node and insert it in the specified position
  • Index ==0 Inserts an element at position 0. First points to the new node, and next points to the node that first pointed to before
  • index! =0, find oldNode before the new node, oldNode’s next points to the new node, and the new node’s next points to the node oldNode pointed to before.

3.8, delete the index element

Public E remove(int index) {// Check whether the index exceeds the rangeCheck(index); Node<E> old = first; If (index == 0) {first = first.next; if (index == 0) {first = first.next; }else {// find the previous element Node<E> prev = Node (index - 1); // Record the node to be deleted old = prev.next; Prev. next = old.next; } // size-1 size--; // Return old. Element; }Copy the code
  • When index is 0, you simply point next of first to the node whose index is “1”
  • If the index is not 0, you need to find only the previous node of the index and point to the next node of the index

3.9, View the index of the element

private static final int ELEMENT_ON_FOUND = -1; Public int indexOf(E element) {// add Node<E> Node = first; If (element == null) {return index for (int I = 0; i < size; i++) { if (node.element == null) return i; node = node.next; } }else { for (int i = 0; i < size; If (element.equals(node.element)) return I; if (element.equals(node.element)) return I; node = node.next; }} return ELEMENT_ON_FOUND return ELEMENT_ON_FOUND; }Copy the code
  • Iterate through all the elements of the node, find the corresponding index position, return good

4. Algorithmic interview questions

4.1, LeetCode–237. Remove nodes in the linked list

Interview address:Leetcode-cn.com/problems/de…

Analysis:

  1. First, analyze the code and give us the node we are currently removing. Before deleting a node, we first found the node (oldNode) before the node to be deleted. Next of oldNode points to the next node after the current node.
  2. Now we only have the current node, so we need to think differently.

Answer:

  1. We just need to overlay the element of the current node with the element next to it. Point next of the current node to next of the next node.

    public class ListNode { int val; ListNode next; ListNode(int x) { val = x; }}

    public void deleteNode(ListNode* node) {

    node.val = node.next.val; node.next = node.next.next; }

4.2, Leetcode – Sword refers to Offer 24. Reverse linked list

Interview questions link:Leetcode-cn.com/problems/fa…

Analysis:

  • They give us a head node, and after the inversion, we want to return the new head node.

Solution 1: Recursion

public ListNode reverseList(ListNode head) { if(head == null || head.next == null) return head; // When head or head.next is null, return head ListNode newHead = reverseList(head.next); // Call reverseList and reverse the element after head head.next-next = head; // reverse head head. Next = null; //head.next points to null. return newHead; }Copy the code
  1. Call the reverseList reverse function to reverse all elements after head
  2. Inversion of the head. Head. next is the nextNode after head. Nextnode. next points to head.
  3. Point next of head to null.

Solution two: plug method

public ListNode reverseList(ListNode head) { ListNode newHead = null; while(head ! = null){ ListNode temp = head.next; head.next = newHead; newHead = head; head = temp; } return newHead; }Copy the code

  • Create temporary node newHead=null, the next node of head

  • Point head. Next to newHead first

  • NewHead points to the current head

  • The current head points to the node where Temp is located.

4.3, Leetcode -141. Whether linked lists have rings

Title link: leetcode-cn.com/problems/li…

Analysis:

  • Pass a head node to check if the list has a ring, return bool

public boolean hasCycle(ListNode head) { if (head == null || head.next == null ) return false; // create a slow node ListNode slow = head; ListNode fast = head. Next; ListNode fast = head. while (fast ! = null && fast.next ! If (slow == fast) return true; // Slow nodes go one at a time slow = slow. Next; // Fast node goes two at a time fast = fast.next-next; } return false; }Copy the code

Answer: fast and slow pointer method

  • Create a slow node as slow and a fast node as fast
  • Slow on a slow node goes next at a time, fast on a fast node once