❝

This is the “24th” original article published by Throwable Digest on the album Algorithmic.

❞


The premise

Today, WHEN I was having lunch, I checked the public account of technology type, and saw that a senior had passed Ant’s high P interview. One question examined the algorithm of searching the nodes in the middle of a single linked list. Looking at the algorithm, I found the solution interesting, so I tried to reproduce it here.

scenario

Interviewer: How do I access the middle nodes of the list?

Big X: Simple implementation, traversing the entire list, then calculating the length of the list, and traversing the second time to find the data in the middle.

Interviewer: How to solve the problem that you can only go through the list once?

Big GUY X: Two Pointers can be established, one pointer traverses two nodes at a time, and the other node traverses one node at a time. When the fast pointer traverses the empty node, the slow pointer points to the middle position of the linked list. The algorithm to solve the problem here is called “fast and slow pointer”.

analyse

Let’s set the length of a single list to be at least 3, so it’s easier to analyze the algorithm. Let’s simply assume a single linked list of length 3 as follows:

j-a-l-f-l-1.png

If we were to visit an intermediate node, we would end up with n2, which is n2.

If the length of a singly linked list is even, which is assumed to be 4, then the following:

j-a-l-f-l-2.png

If we were to visit the intermediate nodes, we would end up with n2 and N3 nodes, which would be n2 and n3.

Define the Node class Node as follows:

@Data
private static class Node<T> {
    
    / * ** The value of the current node* /  private T value;   / * ** Reference to the next node* /  private Node<T> next; } Copy the code

We can easily construct a single linked list as follows:

private static Node<String> buildLinkedList(int len) {
    Node<String> head = new Node<>();
    head.setValue("n1");
    Node<String> tail = head;
    for (int i = 1; i < len; i++) {
 Node<String> node = new Node<>();  node.setValue("n" + (i + 1));  tail.setNext(node);  tail = node;  }  return head; } Copy the code

Then we can write a method to search for intermediate nodes. First, write “scheme 1” that calculates the length by traversing the linked list, and then traverses the linked list to get intermediate nodes:

    private static List<String> searchByTraversal(Node<String> head) {
        List<String> result = new ArrayList<>(2);
        Node<String> search = head;
        int len = 1;
        // Calculate the length of the linked list for the first time
 while(search.getNext() ! =null) {  search = search.getNext();  len++;  }  int index = 0;  int mid;  search = head;  // The list length is even  if ((len & 1) = =0) {  mid = len / 2 - 1;  while(search.getNext() ! =null) {  if (mid == index) {  result.add(search.getValue());  result.add(search.getNext().getValue());  }  search = search.getNext();  index++;  }  } else {  mid = (len - 1) / 2;  while(search.getNext() ! =null) {  if (mid == index) {  result.add(search.getValue());  }  search = search.getNext();  index++;  }  }  return result;  } Copy the code

Write a main method to try it out:

public static void main(String[] args) throws Exception {
    Node<String> head = buildLinkedList(11);
    System.out.println(searchByTraversal(head));
    head = buildLinkedList(12);
    System.out.println(searchByTraversal(head));
}  // Output the result [n6] [n6, n7] Copy the code

Assuming that the length of the linked list is N (n > 0), the total number of elements to be traversed twice is as follows:

  • The first time you walk through the list, you compute the length, you have to walk throughnAn element.
  • The second time I have to iteraten/2Three elements (innWhen the value is relatively large, the effect of addition and subtraction is not significant).

In this scheme, the final time complexity must be greater than O(n). Therefore, we need to consider the optimization scheme. We only need to traverse the linked list once to locate the middle node value. This is scheme 2: “fast or slow pointer”.

A “Fast Pointer” simply defines two Pointers. When traversing a linked list, a Fast Pointer always traverses two elements while a Slow Pointer always traverses one element. When the fast pointer completes traversing the list, the slow pointer points to the middle node of the list. The algorithm is as follows:

/ * ** Search based on fast and slow Pointers* /
private static List<String> searchByFastSlowPointer(Node<String> head) {
    List<String> result = new ArrayList<>();
 // fast pointer  Node<String> fp = head;  // slow pointer  Node<String> sp = head;  int len = 1;  while (null! = fp.getNext()) { if(fp.getNext().getNext() ! =null) {  fp = fp.getNext().getNext();  sp = sp.getNext();  len += 2;  } else {  fp = fp.getNext();  len += 1;  }  }  // The list length is even  if ((len & 1) = =0) {  result.add(sp.getValue());  result.add(sp.getNext().getValue());  } else {  result.add(sp.getValue());  }  return result; } Copy the code

Write a main method to try it out:

public static void main(String[] args) throws Exception {
    Node<String> head = buildLinkedList(11);
    System.out.println(searchByFastSlowPointer(head));
    head = buildLinkedList(12);
    System.out.println(searchByFastSlowPointer(head));
}  // Output the result [n6] [n6, n7] Copy the code

Because the fast and slow pointer scheme is used, the list is traversed only once, and since the fast pointer is traversed two elements at a time, the final time complexity is less than O(n).

Application scenarios of fast and slow Pointers

The application scenarios of the fast and slow Pointers are as follows:

  1. Find the midpoint of the list.
  2. Determine if there are rings in the linked list.
  3. Delete the penultimate from the linked listxA node.

The first scenario has been analyzed as a recovery case, and the second and third scenarios are analyzed below.

Determine if there are rings in the linked list

Assume that the linked list has 6 nodes (head node n1, tail node N6) and has formed a ring (the next node of N6 is N1) :

j-a-l-f-l-3.png

Every time how using a pointer, pointer quickly traverse the meeting is more than one element, slow pointer this way, if the list has been cyclization, no matter how many fast Pointers and slow between pointer apart nodes, fast pointer can always catch up with the slow pointer (slow fast pointer and pointer to the same node), this time you can judge the list have ring formation; Otherwise the fast pointer will jump out of the loop after one iteration and will never “overlap” with the slow pointer. The crude implementation is as follows:

// Check whether the linked list has a ring
private static boolean cyclic(Node<String> head) {
    // fast pointer
    Node<String> fp = head;
    // slow pointer
 Node<String> sp = head;  while(fp.getNext() ! =null) {  fp = fp.getNext().getNext();  sp = sp.getNext();  if (sp.equals(fp)) {  return true;  }  }  return false; }  // Create a circular list private static Node<String> buildCyclicLinkedList(int len) {  Node<String> head = new Node<>();  head.setValue("n1");  Node<String> tail = head;  for (int i = 1; i < len; i++) {  Node<String> node = new Node<>();  node.setValue("n" + (i + 1));  tail.setNext(node);  tail = node;  }  tail.setNext(head);  return head; } Copy the code

Test it out:

public static void main(String[] args) throws Exception {
    Node<String> head = buildCyclicLinkedList(11);
    System.out.println(cyclic(head));
    head = buildLinkedList(11);
    System.out.println(cyclic(head));
}  // Output the result true false Copy the code

Delete the NTH last node in the linked list

This is an algorithm problem on LeetCode, which uses the method of adding the fast and slow pointer to the virtual head node, only one traversal can be solved. Here’s the solution from the most liked answers:

❝

The above algorithm can be optimized to use only one traversal. We can use two Pointers instead of one. The first pointer moves n+1 step forward from the beginning of the list, while the second pointer starts at the beginning of the list. Now, these two Pointers are separated by n nodes. We keep this constant interval by moving both Pointers forward at the same time until the first pointer reaches the last node. The second pointer points to the NTH node from the last node. We relink the next pointer to the node referenced by the second pointer to the node next to that node.

❞

Algorithm diagram:

j-a-l-f-l-4.png

The algorithm code is as follows:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode first = dummy;
    ListNode second = dummy;
 // Advances first pointer so that the gap between first and second is n nodes apart  for (int i = 1; i <= n + 1; i++) {  first = first.next;  }  // Move first to the end, maintaining the gap  while(first ! =null) {  first = first.next;  second = second.next;  }  second.next = second.next.next;  return dummy.next; } Copy the code

The time complexity is O(L), where L is the length of the list.

summary

In view of the algorithm is relatively weak, see these relatively practical problems and solutions, or worth deducting and learning.

References:

  • Remove Nth Node From End of List

(The cover image of C-2-D E-A-20190510 R-A-20200717 is from “Sword God Domain”.)