Basic Data Structures - Chained Tables

linked list

1) General

define

In computer science, a chained table is a linear collection of data elements, each of whose elements points to the next, with elements stored discontinuously

In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.

Can be categorized as[^5]

• A one-way chained table, where each element only knows who its next element is

• A bi-directional chained table, where each element knows its previous and next elements

! [Bidirectional chained table]](/blog/1975191/202409/)

• The tail node of a circular chain table points to null, whereas the tail node of a circular chain table points to the head node.

There is also a special kind of node called Sentinel node, also called Dummy node, which does not store data and is usually used as head and tail to simplify the boundary judgment, as shown in the following figure

Random Access Performance

Find by index, time complexity\(O(n)\)

Insertion or Deletion Performance

• Starting position:\(O(1)\)
• End position: if the tail node is known to be\(O(1)\)I don't know if the tail node is\(O(n)\)
• Middle position: find time according to index +\(O(1)\)

2) Unidirectional chained tables

Based on the definition of a unidirectional chain table, first define a class Node that stores the value and next pointers, and a reference to the head node.

public class SinglyLinkedList {
    
    private Node head; // head node
    
    private static class Node { // nodal category
        int value;
        Node next;

        public Node(int value, Node next) {
             = value;
             = next;
        }
    }
}

• Node is defined as an inner class to externallyharbor (i.e. keep sth hidden)There's no need for the class user to care about the Node structure.
• is defined as a static internal class because the NodeunnecessaryRelated to SinglyLinkedList instances, multiple SinglyLinkedList instances can share the Node class definition.

Header Additions

public class SinglyLinkedList {
    // ...
    public void addFirst(int value) {
		 = new Node(value, );
    }
}

• If == null, the new node points to null and is used as the new
• If ! = null, the added node points to the original , and is used as the new
  • Note that assignment operations are executed in right-to-left order.

while traversing

public class SinglyLinkedList {
    // ...
    public void loop() {
        Node curr = ;
        while (curr != null) {
            // do something
            curr = ;
        }
    }
}

for traversal

public class SinglyLinkedList {
    // ...
    public void loop() {
        for (Node curr = ; curr != null; curr = ) {
            // do something
        }
    }
}

• Both of the above traversals can take theto doPassed in as a Consumer function
  • The rules for Consumer areone parameter，No return valueSo methods like ::println are Consumer
  • When you call Consumer, pass it the current node as an argument

Iterator traversal

public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    private class NodeIterator implements Iterator<Integer> {
        Node curr = head;
        
        public boolean hasNext() {
            return curr != null;
        }

        public Integer next() {
            int value = ;
            curr = ;
            return value;
        }
    }
    
    public Iterator<Integer> iterator() {
        return new NodeIterator();
    }
}

• hasNext is used to determine if it is still necessary to call next.
• Next, do two things.
  • Returns the value of the current node
  • Pointing to the next node
• NodeIterator to be defined asNon-static internal classes, because it is associated with a SinglyLinkedList instance and is an iteration over some SinglyLinkedList instance

recursive traversal

public class SinglyLinkedList implements Iterable<Integer> {
    // ...
    public void loop() {
        recursion();
    }

    private void recursion(Node curr) {
        if (curr == null) {
            return;
        }
        // Do something up front.
        recursion();
        // Do something back there.
    }
}

Add at the end

public class SinglyLinkedList {
    // ...
    private Node findLast() {
        if ( == null) {
            return null;
        }
        Node curr;
        for (curr = ;  != null; ) {
            curr = ;
        }
        return curr;
    }
    
    public void addLast(int value) {
        Node last = findLast();
        if (last == null) {
            addFirst(value);
            return;
        }
         = new Node(value, null);
    }
}

• Note that to find the last node, the termination condition is == null
• The reason for splitting into two methods is for code clarity and to allow reuse after findLast().

Tail to add multiple

public class SinglyLinkedList {
    // ...
	public void addLast(int first, int... rest) {
        
        Node sublist = new Node(first, null);
        Node curr = sublist;
        for (int value : rest) {
             = new Node(value, null);
            curr = ;
        }
        
        Node last = findLast();
        if (last == null) {
             = sublist;
            return;
        }
         = sublist;
    }
}

• Start with a sublist
• Then add as a whole

Get by index

public class SinglyLinkedList {
    // ...
	private Node findNode(int index) {
        int i = 0;
        for (Node curr = ; curr != null; curr = , i++) {
            if (index == i) {
                return curr;
            }
        }
        return null;
    }
    
    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(("index [%d] unlawful%n", index));
    }
    
    public int get(int index) {
        Node node = findNode(index);
        if (node != null) {
            return ;
        }
        throw illegalIndex(index);
    }
}

• Similarly, sub-methods enable reuse

stick

public class SinglyLinkedList {
    // ...
	public void insert(int index, int value) {
        if (index == 0) {
            addFirst(value);
            return;
        }
        Node prev = findNode(index - 1); // Find the previous node
        if (prev == null) { // can't find
            throw illegalIndex(index);
        }
         = new Node(value, );
    }
}

• Insertions, including the following deletions, must find the previous node

removing

public class SinglyLinkedList {
    // ...
	public void remove(int index) {
        if (index == 0) {
            if ( != null) {
                 = ;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = ) != null) {
             = ;
        } else {
            throw illegalIndex(index);
        }
    }
}

• The first if block corresponds to the removeFirst case
• The last if block corresponds to the case where there are at least two nodes.
  • Not only determine that the previous node is non-empty, but also ensure that the current node is non-empty

3) Unidirectional chained tables (with sentinels)

Looking at the previous implementation of unidirectional chain lists, I found that almost every method has code that determines whether it is head or not, can it be simplified?

A special Node that is not involved in data storage is used as a Sentinel, which is generally called a Sentinel or Dumb Element, and a chained table that has a Sentinel node is called a Headed Chained Table

public class SinglyLinkedListSentinel {
    // ...
    private Node head = new Node(Integer.MIN_VALUE, null);
}

• It doesn't matter what value is stored, because it won't be used.

With the addition of the sentinel node, the code becomes simpler, starting with a couple of tool methods

public class SinglyLinkedListSentinel {
    // ...
    
    // Get node by index
    private Node findNode(int index) {
        int i = -1;
        for (Node curr = ; curr != null; curr = , i++) {
            if (i == index) {
                return curr;
            }
        }
        return null;
    }
    
    // Get the last node
    private Node findLast() {
        Node curr;
        for (curr = ; != null; ) {
            curr = ;
        }
        return curr;
    }
}

• findNode is similar to the previous one, except that the initial value of i is set to -1 to correspond to the sentinel, and the actual index passed in is also\([-1, \infty)\)
• findLast will never return null, even if there are no other nodes, it will return the sentinel as the last node.

This simplifies the code to

public class SinglyLinkedListSentinel {
    // ...
    
    public void addLast(int value) {
        Node last = findLast();
        /*
        pre-alteration
        if (last == null) {
             = new Node(value, null);
            return;
        }
        */
         = new Node(value, null);
    }
    
    public void insert(int index, int value) {
        /*
        pre-alteration
        if (index == 0) {
             = new Node(value, );
            return;
        }
        */
        // index transmitted inwards 0 hour，Returning is the Sentinel
        Node prev = findNode(index - 1);
        if (prev != null) {
             = new Node(value, );
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void remove(int index) {
        /*
        pre-alteration
        if (index == 0) {
            if ( != null) {
                 = ;
                return;
            } else {
                throw illegalIndex(index);
            }
        }
        */
        // index transmitted inwards 0 hour，Returning is the Sentinel
        Node prev = findNode(index - 1);
        Node curr;
        if (prev != null && (curr = ) != null) {
             = ;
        } else {
            throw illegalIndex(index);
        }
    }
    
    public void addFirst(int value) {
        /*
        pre-alteration
         = new Node(value, );
        */
		 = new Node(value, );
        // It can also be regarded as insert special case, assume (office) insert(0, value);
    }
}

• For deletion, as stated earlier [the last if block corresponds to the case where you have to have at least two nodes], now with sentinels, you have two nodes.

4) Bidirectional chained tables (with sentinels)

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    private final Node head;
    private final Node tail;

    public DoublyLinkedListSentinel() {
        head = new Node(null, 666, null);
        tail = new Node(null, 888, null);
         = tail;
         = head;
    }

    private Node findNode(int index) {
        int i = -1;
        for (Node p = head; p != tail; p = , i++) {
            if (i == index) {
                return p;
            }
        }
        return null;
    }

    public void addFirst(int value) {
        insert(0, value);
    }

    public void removeFirst() {
        remove(0);
    }

    public void addLast(int value) {
        Node prev = ;
        Node added = new Node(prev, value, tail);
         = added;
         = added;
    }

    public void removeLast() {
        Node removed = ;
        if (removed == head) {
            throw illegalIndex(0);
        }
        Node prev = ;
         = tail;
         = prev;
    }

    public void insert(int index, int value) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node next = ;
        Node inserted = new Node(prev, value, next);
         = inserted;
         = inserted;
    }

    public void remove(int index) {
        Node prev = findNode(index - 1);
        if (prev == null) {
            throw illegalIndex(index);
        }
        Node removed = ;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        Node next = ;
         = next;
         = prev;
    }

    private IllegalArgumentException illegalIndex(int index) {
        return new IllegalArgumentException(
                ("index [%d] unlawful%n", index));
    }

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<Integer>() {
            Node p = ;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public Integer next() {
                int value = ;
                p = ;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
             = prev;
             = value;
             = next;
        }
    }
}

5) Ring Chained Table (with Sentinel)

Bidirectional circular chain table with sentinel, when the sentinelBoth as the head and the tail

reference implementation

public class DoublyLinkedListSentinel implements Iterable<Integer> {

    @Override
    public Iterator<Integer> iterator() {
        return new Iterator<>() {
            Node p = ;

            @Override
            public boolean hasNext() {
                return p != sentinel;
            }

            @Override
            public Integer next() {
                int value = ;
                p = ;
                return value;
            }
        };
    }

    static class Node {
        Node prev;
        int value;
        Node next;

        public Node(Node prev, int value, Node next) {
             = prev;
             = value;
             = next;
        }
    }

    private final Node sentinel = new Node(null, -1, null); // sentinel

    public DoublyLinkedListSentinel() {
         = sentinel;
         = sentinel;
    }

    /**
     * Add to the first
     * @param value value to be added
     */
    public void addFirst(int value) {
        Node next = ;
        Node prev = sentinel;
        Node added = new Node(prev, value, next);
         = added;
         = added;
    }

    /**
     * Add to last
     * @param value value to be added
     */
    public void addLast(int value) {
        Node prev = ;
        Node next = sentinel;
        Node added = new Node(prev, value, next);
         = added;
         = added;
    }
    
    /**
     * Delete the first
     */
    public void removeFirst() {
        Node removed = ;
        if (removed == sentinel) {
            throw new IllegalArgumentException("illegally");
        }
        Node a = sentinel;
        Node b = ;
         = b;
         = a;
    }

    /**
     * Delete the last
     */
    public void removeLast() {
        Node removed = ;
        if (removed == sentinel) {
            throw new IllegalArgumentException("illegally");
        }
        Node a = ;
        Node b = sentinel;
         = b;
         = a;
    }

    /**
     * Delete nodes based on value
     * <p>hypothesis value in a linked list as key, unique</p>
     * @param value Value to be deleted
     */
    public void removeByValue(int value) {
        Node removed = findNodeByValue(value);
        if (removed != null) {
            Node prev = ;
            Node next = ;
             = next;
             = prev;
        }
    }

    private Node findNodeByValue(int value) {
        Node p = ;
        while (p != sentinel) {
            if ( == value) {
                return p;
            }
            p = ;
        }
        return null;
    }

}

school work exercises

E01. Reversing unidirectional chain tables - Leetcode 206

Stress Buckling Topic206. Inverted chain tables - LeetCode

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Input : [1,2]
Output: [2,1]

Input: []
Output: []

Method 1

Constructs a new linked table fromold linked listGet each node in turn and create new nodes to add to thenew linked listheader, the new chain table will be inverted when it is completed.

public ListNode reverseList(ListNode o1) {
    ListNode n1 = null;
    ListNode p = o1;
    while (p != null) {
        n1 = new ListNode(, n1);
        p = ;
    }
    return n1;
}

Evaluation: Simple and straightforward, that is, you have to create new node objects

Method 2

Similarly to method 1, construct a new linked table from theold linked list headerRemove the node, add it to thenew linked list headerThe difference is that the original topic does not provide a container class for the outer layer of the node, but here we provide one, and the other difference is that we do not construct a new node.

static class List {
    ListNode head;

    public List(ListNode head) {
         = head;
    }

    public ListNode removeFirst(){
        ListNode first = head;
        if (first != null) {
            head = ;
        }
        return first;
    }

    public void addFirst(ListNode first) {
         = head;
        head = first;
    }
}

coding

public ListNode reverseList(ListNode head) {
    List list1 = new List(head);
    List list2 = new List(null);
    ListNode first;
    while ((first = ()) != null) {
        (first);
    }
    return ;
}

Verdict: more object-oriented, more likely to do so if actually writing code rather than brushing up on problems

Method 3

Recursively, in the(of a responsibility) be taken care of bylet sb do sth at the right time\(5 \rightarrow 4\)，\(4 \rightarrow 3\) ...

First, write a recursive method with the return value used to get to the last node

public ListNode reverseList(ListNode p) {
    if (p == null || == null) { // less than two nodes
        return p; // last node
    }
    ListNode last = reverseList(); return last; }
    return last; }
}

• Note 1: The recursion termination condition is == null, which aims to end the recursion at the last node, unlike the previous recursive traversal
• Note 2: You need to consider the case of an empty linked table, i.e., p == null.

You can test it first.

ListNode o5 = new ListNode(5, null);
ListNode o4 = new ListNode(4, o5);
ListNode o3 = new ListNode(3, o4);
ListNode o2 = new ListNode(2, o3);
ListNode o1 = new ListNode(1, o2);
ListNode n1 = new E01Leetcode206().reverseList(o1);
(n1);

printable

[5]

followingpseudocodecall procedure, assuming that the nodes are respectively\(1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)Ignore the return value first.

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    reverseList(ListNode p = 3) {
    reverseList(ListNode p = 4) {
    reverseList(ListNode p = 5) {
    if (p == null || == null) {
                        return p; // return 5
                    }
}
                // p is 4, it's 5
}
            // p is 3, it's 4
}
        // And p is 2, and it's 3.
}
    // And p is 1, and it's 2.
}

Next, starting with p = 4, to make the\(5 \rightarrow 4\)，\(4 \rightarrow 3\) ...

reverseList(ListNode p = 1) {
    reverseList(ListNode p = 2) {
    reverseList(ListNode p = 3) {
    reverseList(ListNode p = 4) {
    reverseList(ListNode p = 5) {
    if (p == null || == null) {
                        return p; // return 5
                    }
}
                // Now p is 4, it's 5, so to make 5 point to 4, write =p
                // Also note that 4 must point to null, otherwise it's a dead link.
}
            // p is 3, it's 4.
}
        // p is 2, it's 3.
}
    // And p is 1, and it's 2.
}

The final code is:

public ListNode reverseList(ListNode p) {
    if (p == null || == null) { // less than two nodes
        return p; // last node
    }
    ListNode last = reverseList().
     = p; // last node; }
     = p; = null; return last; return p; // Last node.
    return last; }
}

Q: Why can't thegradually increase or decreaseThe process in reverse order?

A: For example

• $ 1 \rightarrow 2 \rightarrow 3 $ If the handing process lets the\(2 \rightarrow 1\) So, at this point.\(2 \rightarrow 3\) It's covered. I don't know who to hand it to next.
• And when you return, let\(3 \rightarrow 2\) It won't affect the previous layer.\(1 \rightarrow 2\)

Evaluation: unidirectional chained lists do not have a prev pointer, but take advantage of the recursive nature [remembering] who the two neighboring nodes of the chained list are each time the list is invoked

Method 4

Each time you get a second node from the chain, disconnect it from the chain and insert it into the head until it is null.

1. Set pointers o1 (old header), n1 (new header), o2 (old old second), pointing to the first, first, and second nodes, respectively

\(\frac{n1 \ o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

2. Disconnect the o2 node from the chain table, i.e., the o1 node points to the third node

$ \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null$ ，\(\frac{o2}{2}\)

3. o2 nodes are chained into the head of the chain table, i.e., the

\(\frac{o2}{2} \rightarrow \frac{n1 \ o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

4. n1 pointing to o2

\(\frac{n1 \ o2}{2} \rightarrow \frac{o1}{1} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

5. o2 points to the next node of o1, i.e.

\(\frac{n1}{2} \rightarrow \frac{o1}{1} \rightarrow \frac{o2}{3} \rightarrow 4 \rightarrow 5 \rightarrow null\)

6. Repeat the above\(2\sim5\) step until o2 points to null

7. Boundary conditions should also be considered, i.e. the above logic is not necessary when there are less than two elements in the chain table

reference answer

public ListNode reverseList(ListNode o1) {
    if (o1 == null || == null) { // less than two nodes
        return o1; }
    }
    ListNode o2 = ;
    ListNode n1 = o1; while (o2 !
    while (o2 ! = null) {
         o2 = ; ListNode n1 = o1; while (o2 != null) {
         
        
        o2 = ;
    }
    return n1; }
}

Method 5

The idea is to keep moving from the beginning of the table 2 to the beginning of the table 1.

1. n1 points to null, which stands fornew linked listThere is no element at the beginning. o1 points tooriginal linked listfirst node of sth.

\(\frac{n1}{null}\)，\(\frac{o1}{1} \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

2. Start the loop. o2 is pointing tooriginal linked listsub-node

\(\frac{n1}{null}\)，\(\frac{o1}{1} \rightarrow \frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

3. move (house)

\(\frac{o1}{1} \rightarrow \frac{n1}{null}\) ， \(\frac{o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

4. pointer reset (computing)

\(\frac{n1}{1} \rightarrow null\) ， \(\frac{o1 \ o2}{2} \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow null\)

5. repeatable\(2\sim4\) surname Bu, a.k.a. "walk" or "step" in Chinese history
6. Exit loop when o1 = null

reference answer

public ListNode reverseList(ListNode o1) {
    if (o1 == null ||  == null) {
        return o1;
    }
    ListNode n1 = null;
    while (o1 != null) {
        ListNode o2 = ;
         = n1;
        n1 = o1;
        o1 = o2;
    }
    return n1;
}

Evaluation: Essentially the same as Method 2, except that Method 2 is more object-oriented.

E02. Deletion of nodes by value - Leetcode 203

for example

Input: head = [1,2,6,3,6], val = 6
Output: [1,2,3]

Input: head = [], val = 1
Output: []

Input: head = [7,7,7,7], val = 7
Output: []

Method 1

In the diagram s stands for sentinel sentinel (if no sentinel is added, deletion of the first node is handled specially), e.g. to delete 6

p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• If p2 is not equal to the target, then p1, p2 move backward continuously

	 p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

	 	  p1   p2
s -> 1 -> 2 -> 6 -> 3 -> 6 -> null

• p2 == 6, delete it, noting that p1 stays the same and p2 is shifted back.

	 	  p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 is not equal to the target, then p1, p2 keep moving back.

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> 6 -> null

• p2 == 6, delete it, noting that p1 stays the same and p2 is shifted back.

	 	  	   p1   p2
s -> 1 -> 2 -> 3 -> null

• p2 == null to exit the loop

final code

public ListNode removeElements(ListNode head, int val) {
    ListNode sentinel = new ListNode(-1, head);
    ListNode p1 = sentinel;
    ListNode p2;
    while ((p2 = ) != null) {
        if ( == val) {
             = ;
        } else {
            p1 = ;
        }
    }
    return ;
}

Method 2

The idea is that the recursive function is responsible for returning: a child list of completed deletions, starting with the current node (me)

1. If I am equal to v, I should return the next node recursion result
2. If I am not equal to v, I should be returned, but my next should be updated (so that I can take the subsequently deleted sub-links with me)

removeElements(ListNode p=1, int v=6){
    =removeElements(ListNode p=2, int v=6){
    	=removeElements(ListNode p=6, int v=6){
    		removeElements(ListNode p=3, int v=6){
    			=removeElements(ListNode p=6, int v=6){
    				removeElements(ListNode p=null, int v=6){
    					// No nodes,come (or go) back
                        return null
					}
				}
                return 3
			}
		}
        return 2
    }
    return 1
}

coding

public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return null;
    }
    if ( == val) {
        return removeElements(, val);
    } else {
         = removeElements(, val);
        return head;
    }
}

E03. Delete Countdown Node - Leetcode 19

for example

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input: head = [1], n = 1
Output: []

Input: head = [1,2], n = 1
Output: [1]

Also the title suggests

• At least one node of a chained table
• n Only within reason

Method 1

Idea, write a recursive function that returns the inverse ordinal number of the next node

recursion(ListNode p=1, int n=2) {
    recursion(ListNode p=2, int n=2) {
    	recursion(ListNode p=3, int n=2) {
    		recursion(ListNode p=4, int n=2) {
    			recursion(ListNode p=5, int n=2) {
    				recursion(ListNode p=null, int n=2) {
    					return 0; // Inner most serial number0
					}
                    return 1; // Previous Return Value+1
				}
                return 2;
			}
            if(return value == n == 2) {
                // removing next
            }
            return 3;
		}
        return 4;
	}
    return 5;
}

However, one problem with the above code is that if the deletion is of the first node, it does not have a previous node, so it can be solved by adding a sentinel

coding

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode sentinel = new ListNode(-1, head);
    recursion(sentinel, n);
    return ;
}

public int recursion(ListNode p, int n) {
    if (p == null) {
        return 0;
    }
    int nth = recursion(, n);
    if (nth == n) {
         = ;
    }
    return nth + 1;
}

Q: Aren't you afraid of empty hands?

A：

• p is the previous node of the node to be deleted, and if you can recursively go back to p, then it must have a value, not null.
• and the title states that n >=1 does not make nth == 0 point to the last null

Method 2

Fast and slow pointers, p1 points to the previous node to be abridged, p2 goes n + 1 steps first.

i=0
p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

     i=1
     p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

          i=2
          p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               i=3 From this point on p1 p2 shift to the right until p2 reaches the end.
p1 p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

               p1 p2
s -> 1 -> 2 -> 3 -> 4 -> 5 -> null

coding

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2 = s;
    for (int i = 0; i < n + 1; i++) {
        p2 = ;
    }
    while (p2 != null) {
        p1 = ;
        p2 = ;
    }
     = ;
    return ;
}

Method 3

public ListNode removeNthFromEnd(ListNode head, int n) {
    Composite c = recursion(head, n);
    return ;
}

static class Composite {
    ListNode node;
    int nth;

    public Composite(ListNode node, int nth) {
         = node;
         = nth;
    }
}

public Composite recursion(ListNode p, int n) {
    if (p == null) {
        return new Composite(null, 1);
    }
    Composite c = recursion(, n);
    if ( != n) {
         = ;
         = p;
    }
     +=1;
    return c;
}

E04. Ordered Chained Table Deranking - Leetcode 83

for example

Input: head = [1,1,2]
Output: [1,2]

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Attention:Duplicate elements retain a

Method 1

p1   p2
1 -> 1 -> 2 -> 3 -> 3 -> null

• == then delete p2, noting that p1 remains unchanged.

p1   p2
1 -> 2 -> 3 -> 3 -> null

• ! - (GROANS) = then p1, p2 move back.

     p1   p2
1 -> 2 -> 3 -> 3 -> null
         
          p1   p2
1 -> 2 -> 3 -> 3 -> null     

• == then delete p2

          p1   p2
1 -> 2 -> 3 -> null   

• Exit the loop when p2 == null

coding

public ListNode deleteDuplicates(ListNode head) {
    // linked list node < 2
    if (head == null || == null) {
        return head;
    }
    // linked list node >= 2
    ListNode p1 = head;
    ListNode p2;
    while ((p2 = ) != null) {
        if ( == ) {
             = ;
        } else {
            p1 = ;
        }
    }
    return head;
}

Method 2

The recursive function is responsible for returning: a chained list starting from the current node (me), complete with de-duplication

1. If I duplicate next, return next
2. If I am not duplicated by next, return me, but next should be updated.

deleteDuplicates(ListNode p=1) {
    deleteDuplicates(ListNode p=1) {
        =deleteDuplicates(ListNode p=2) {
            =deleteDuplicates(ListNode p=3) {
                deleteDuplicates(ListNode p=3) {
					// Only one node left.，come (or go) back
                    return 3
                }                
            }
            return 2
        }
        return 1
    }
}

coding

public ListNode deleteDuplicates(ListNode p) {
    if (p == null ||  == null) {
        return p;
    }
    if( == ) {
        return deleteDuplicates();
    } else {
         = deleteDuplicates();
        return p;
    }
}

E05. Ordered Chained Table Deranking - Leetcode 82

for example

Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Input: head = [1,1,1,2,3]
Output: [2,3]

Attention:Leave no duplicate element behind

Method 1

The recursive function is responsible for returning: a chained list starting from the current node (me), complete with de-duplication

1. If I duplicate next, keep finding the next node that doesn't duplicate, whichever one it returns
2. If I am not duplicated by next, return me and update next.

deleteDuplicates(ListNode p = 1) {
    // Find the next one that doesn't repeat.
	deleteDuplicates(ListNode p = 1) {
        deleteDuplicates(ListNode p = 1) {
			deleteDuplicates(ListNode p = 2) {
                =deleteDuplicates(ListNode p = 3) {
					// Only one node left.，come (or go) back
                    return 3
                }
                return 2
			}
        }
    }
}

coding

public ListNode deleteDuplicates(ListNode p) {
    if (p == null ||  == null) {
        return p;
    }
    if ( == ) {
        ListNode x = ;
        while (x != null &&  == ) {
            x = ;
        }
        return deleteDuplicates(x);
    } else {
         = deleteDuplicates();
        return p;
    }
}

Method 2

p1 is the last node to be deleted, and each loop compares the values of p2 and p3.

• If p2 duplicates the value of p3, then p3 continues to move back until it finds a node that does not duplicate p2, and p1 points to p3 to complete the deletion.
• If the values of p2 and p3 are not duplicated, p1, p2, and p3 are shifted back one place, and the above operation continues
• p2 or p3 is null to exit the loop.
  • The case where p2 is null, e.g., a linked table is 1 1 1 null.

p1 p2 p3
s, 1, 1, 1, 2, 3, null

p1 p2    p3
s, 1, 1, 1, 2, 3, null

p1 p2       p3
s, 1, 1, 1, 2, 3, null

p1 p3
s, 2, 3, null

p1 p2 p3
s, 2, 3, null

   p1 p2 p3
s, 2, 3, null

coding

public ListNode deleteDuplicates(ListNode head) {
    if (head == null ||  == null) {
        return head;
    }

    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2;
    ListNode p3;
    while ((p2 = ) != null && (p3 = ) != null) {
        if ( == ) {
            while ((p3 = ) != null 
                   &&  == ) {
            }
             = p3;
        } else {
            p1 = ;
        }
    }
    return ;
}

E06. Merging Ordered Chained Tables - Leetcode 21

precedent

Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: l1 = [], l2 = []
Output: []

Input: l1 = [], l2 = [0]
Output: [0]

Method 1

• Chain whoever is smaller to p. Both p and smaller are shifted back one place.
• When one of p1 and p2 is null, exit the loop and give the chain that is not null to p.

p1
1	3	8	9	null

p2
2	4	null

p		
s	null

coding

public ListNode mergeTwoLists(ListNode p1, ListNode p2) {
    ListNode s = new ListNode(-1, null);
    ListNode p = s;
    while (p1 != null && p2 != null) {
        if ( < ) {
             = p1;
            p1 = ;
        } else {
             = p2;
            p2 = ;
        }
        p = ;
    }
    if (p1 != null) {
         = p1;
    }
    if (p2 != null) {
         = p2;
    }
    return ;
}

• You can verify it yourself.precedentmiddle and lower cases

Method 2

The recursive function should return

• smaller one, and recursively connects its remaining nodes to the other one.
• Before returning, update this node's next

mergeTwoLists(p1=[1,3,8,9], p2=[2,4]) {
    =mergeTwoLists(p1=[3,8,9], p2=[2,4]) {
        =mergeTwoLists(p1=[3,8,9], p2=[4]) {            
            =mergeTwoLists(p1=[8,9], p2=[4]) {
                =mergeTwoLists(p1=[8,9], p2=null) {
                    return [8,9]
                }
                return 4
            }
            return 3
        }
        return 2
    }
	return 1
}

E07. Merging Multiple Ordered Chained Tables - Leetcode 23

precedent

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [[1,1,2,3,4,4,5,6]]
Explanation : The array of chained lists is as follows:
[
  1->4->5,
  1->3->4,
  2->6
]
Combining them into an ordered chain list yields.
1->1->2->3->4->4->5->6

Method 1

recursive (calculation)

public ListNode mergeKLists(ListNode[] lists) {
    if ( == 0) {
        return null;
    }
    return split(lists, 0,  - 1);
}

public ListNode split(ListNode[] lists, int i, int j) {
    (i + " " + j);
    if (j == i) {
        return lists[i];
    }
    int m = (i + j) >>> 1;
    return mergeTwoLists(
        split(lists, i, m),
        split(lists, m + 1, j)
    );
}

It can also be solved using a priority queue, which will be discussed later on

E08. Finding the middle node of a chained table - Leetcode 876

for example

Input: [1,2,3,4,5]
Output: node 3 in this list (serialized form: [3,4,5])

Input: [1,2,3,4,5,6]
Output: node 4 in this list (serialized form: [4,5,6])

• even numberWhen nodes are used, the center point is the one to the right of the

Solution: fast and slow pointer, fast pointer two steps at a time, slow pointer one step at a time, when the fast pointer to the end of the chain table, the slow pointer exactly halfway to the chain table

public ListNode middleNode(ListNode head) {
    ListNode p1 = head; // slow pointer，midpoint
    ListNode p2 = head; // fast pointer
    while (p2 != null && != null) {
        p1 = ;
        p2 = ;
        p2 = ;
    }
    return p1;
}

E09. Chained tables of palindromes - Leetcode 234

By palindrome, I mean reading it forward and backward with the same result, for example

[1,2,2,1]
[1,2,3,2,1]

They are all palindromes, not examples of palindromes

[1,2,3,1] -- in reverse -- > [1,3,2,1]

solution (a math problem)

/*
    move1. Find the middle ground.
    move2. Reverse half of the chain table after the midpoint
    move3. Compare the reversed chained table with the original chained table one by one
*/
public boolean isPalindrome(ListNode head) {
    ListNode middle = middle(head);
    ListNode newHead = reverse(middle);
    while (newHead != null) {
        if ( != ) {
            return false;
        }
        newHead = ;
        head = ;
    }
    return true;
}

private ListNode reverse(ListNode o1) {
    ListNode n1 = null;
    while (o1 != null) {
        ListNode o2 = ;
         = n1;
        n1 = o1;
        o1 = o2;
    }
    return n1;
}

private ListNode middle(ListNode head) {
    ListNode p1 = head; // slowly
    ListNode p2 = head; // sharp (of knives or wits)
    while (p2 != null && != null) {
        p1 = ;
        p2 = ;
    }
    return p1;
}

Optimized solution

public boolean isPalindrome(ListNode h1) {
    if (h1 == null || == null) {
        return true; }
    }
    ListNode p1 = h1; // slow pointer, middle point
    ListNode p2 = h1; // fast pointer
    ListNode n1 = null; // new header
    ListNode o1 = h1; // old head
    // Fast and slow pointers to find the halfway point
    while (p2 ! = null && ! = null) {
        p1 = ;
        p2 = ;

        // Reverse the first half
         = n1.
        n1 = o1.
        o1 = p1; }
    }
    if (p2 ! = null) { // odd number of nodes
        p1 = ;
    }
    // Synchronize the comparison of the new header and the second half
    while (n1 ! = null) {
        if ( ! = ) {
            return false; }
        }
        p1 = ;
        n1 = ;
    }
    return true; }
}

E10. Ring-linked tables - Leetcode 141

This, as well as the next question, is actually Floyd's Tortoise and Hare Algorithm[^15]

In addition to the Floyd Ring Determination Algorithm, there are other Ring Determination Algorithms as well, as detailed in/wiki/Cycle_detection

If there is a ring on a chain table, then two pointers traveling at different speeds on the ring must meet at some point. The algorithm is divided into two stages

Stage 1

• The tortoise takes one step at a time. The hare takes two steps at a time.
• When the rabbit can walk to the finish line, there is no loop
• When the hare can catch up with the tortoise, the existence of a ring can be determined

Stage 2

• From their first encounter, the tortoise returns to the starting point and the hare stays in the same position
• The tortoise and the hare both take one step at a time.
• When they meet again, the location will be the entrance to the ring.

Why?

• Let the starting point to the entrance be a step (7 in this case) and the length of a loop around the ring be b (5 in this case).
• in that caseFrom the starting point, go a + n times around the ring to find the ring entrance.
• When we first met
  • The rabbits have traveled a + n laps around the ring (in this case 2 laps) + k, where k is the distance from the entrance to the ring where they met (in this case 3, not important).
  • The tortoise makes a + n laps around the ring (in this case 0 laps) + k, but of course it makes fewer laps than the hare.
  • The hare walks twice as far as the tortoise, so thelost = ♪ The rabbit walks - ♪ The tortoise walks ♪n turns around the ring
• And as previously analyzed, the ring entrance can be found if one walks a + n times around the ring, so starting from the meeting point and taking a step is the ring entrance.

Stage 1 Reference code (determining if there is a ring)

public boolean hasCycle(ListNode head) {
    ListNode h = head; // rabbits
    ListNode t = head; // turtles
    while (h != null && != null) {
        t = ;
        h = ;
        if(h == t){
            return true;
        }
    }
    return false;
}

E11. Ring-linked tables - Leetcode 142

Stage 2 Reference code (find the ring entrance)

public ListNode detectCycle(ListNode head) {
    ListNode t = head; // turtles
    ListNode h = head; // rabbits
    while (h != null && != null) {
        t = ;
        h = ;
        if (h == t) {
            t = head;
            while (true) {
                if (h == t) {
                    return h;
                }
                h = ;
                t = ;
            }
        }
    }
    return null;
}

• There is another extension that can also be solved by using the idea of the judgement loop algorithm: it is the problem 287, finding the number of repetitions

Delete node - Leetcode 237

This question is relatively simple and is left for you to practice on your own

for example

Input: head = [4,5,1,9], node = 5
Output: [4,1,9]


Input: head = [4,5,1,9], node = 1
Output: [4,5,9]

Note: Deleted nodesfaultend node

reference answer

public class Ex1Leetcode237 {
    /**
     /**
     * @param node node to be deleted, the title has already stated that certainly not the last node
     */
    public void deleteNode(ListNode node) {
         = ; // Assign the next node value to the node to be "deleted".
         = ; // Delete the next node.
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null); } public static void main(String[] args) {
        ListNode o4 = new ListNode(4, o5);
        
        
        ListNode o1 = new ListNode(1, o2); ListNode
        (o1);
        new E0xLeetcode237().deleteNode(o3);
        (o1);
    }
}

exports

[1,2,3,4,5]
[1,2,4,5]

Ex2. Common Tailed Chained Tables - Leetcode 160

The original title was calledcross over (e.g. traffic)Chained lists, personally, I find it easier to usecoplanarChained lists are more graphic, and this question is more of a brain teaser, left as an exercise for you!

For example, the two linked lists [1, 2, 4, 5] and [3, 4, 5] in the following figure have the same [4, 5], and node 4 should be returned.

The non-co-terminal case, shown below, returns null

Idea, call the two chained lists a=[1, 2, 4, 5] and b=[3, 4, 5], with N representing null in the figure

1. Iterate over a, and reroute to b when null is encountered.
2. At the same time, iterate over b, and when it encounters null, iterate over a instead.
3. During this process, if theMeet the samenode, that is, to find the target, return can be, as shown in the following figure, the second occurrence of the 4
4. Identical nodes should compare theirreference valueThe numbers in the chart are just to make it easier to differentiate

1	2	4	5	N	3	4	5	N
3	4	5	N	1	2	4	5	N

If two chain lists are of the same length, the target can be found earlier, e.g. a=[1, 4, 5], b=[3, 4, 5], the first occurrence of 4 can be returned

1	4	5	N	3	4	5	N
3	4	5	N	1	4	5	N

In the case of non-common tails, e.g. a=[1, 2, 4], b=[3, 5], you can see that the only equivalent case is to traverse to the last N and exit the loop at that point.

1	2	4	N	3	5	N
3	5	N	1	2	4	N

coding

public ListNode getIntersectionNode(ListNode a, ListNode b) {
    ListNode p1 = a;
    ListNode p2 = b;
    while (true) {
        if (p1 == p2) {
            return p1;
        }
        if (p1 == null) {
            p1 = b;
        } else {
            p1 = ;
        }
        if (p2 == null) {
            p2 = a;
        } else {
            p2 = ;
        }            
    }
}

This article, which has been featured on, my tech siteWe have full interviews with big companies, working technology, architect growth path, and other experiences to share!