preface

Recently is also in the brush algorithm, from the brush question brush began to doubt life, feel good ‘food’, to later slowly found the feeling of writing algorithm, and then to the algorithm produced a great interest. In fact, it was really painful to do the algorithm at the beginning, and the frustration made me very frustrated. But after doing it in the last two weeks, I felt that the algorithm was not so horrible as I imagined, because we don’t need to create the algorithm, we just need to master the ideas and methods of solving problems, and then we can master them with deliberate training.

Here, I suggest you not to brush the algorithm questions directly from the List of LeetCode, because there are too many algorithm questions, it is impossible to brush. Therefore, I suggest you to start from a certain type of question, I suggest to start from the linked list or tree. Here is my reason:

First, as an array type algorithm topic quantity is really too much, and the questions of the form is very much, in a short period of time is very easy to give up, you can’t see your own progress less tree and the algorithm of chain table topic, of the form is not a lot, are relatively is relatively easy to master, in a short period of time can improve yourself the confidence of the algorithm.

Second, like some of the problems of the single linked list, it is very much the use of Pointers, like we do algorithm problems more difficult or some use of Pointers. Although some algorithms can be done with the help of some of the language’s utility classes, they will use extra memory. Some algorithms may require you to use O(1) space complexity, in which case Pointers will be used.

Third, when you finish the single linked list of topics, you will have a preliminary feeling for the use of Pointers, for the back of some algorithm topics is a good help.

So I suggest that if you start brushing, you should start with the linked list.

1. A specified node in the single-linked list needs to be counted backwards

1.1 Solution ideas and code templates

The core of this kind of algorithm problem is the need to locate a specific node location given by the problem. As long as the designated node location is found, the rest of the problem is well solved. I’ve listed a few algorithms in LeetCode below to get a feel for them.

  1. Returns the penultimate KTH node of a linked list
  2. Deletes the penultimate node of the linked list
  3. Rotating list

We do this kind of topic, thinking basically the same, we can make a similar subject summed up a template: this kind of problem frequently used is how quickly a pointer to the problem solving, by how quickly a pointer we want to locate the node position of the operation, find the corresponding position, according to the topic on the corresponding operation. Here I made a simple GIF, first let the fast pointer move k, and then let the fast and slow Pointers move back together, and found the penultimate linked list node.


The template code is as follows:

public static ListNode method(ListNode head, int k) {
// Fast pointer, let it take k steps first,        ListNode fast = head;
        for (int i = 0; i < k; i++) {
            fast = fast.next;
 } When the fast pointer reaches the end of the list, the slow pointer points to the KTH node from the bottom ListNode temp = head; // The first node of the penultimate KTH node you are looking for. Because if you want to operate on the KTH node, you generally need to find the first and foremost node of the KTH node// Delete the KTH node from the list using preNode ListNode preNode = null;  while(fast ! = null ) { preNode = temp;  temp = temp.next;  fast = fast.next;  }  return temp;  } Copy the code

The first algorithm problem, we can solve with this template code above.

In the second algorithm problem, we need to delete the penultimate KTH node, we still use the above code template to find, but here to operate the penultimate KTH node, we must first find the node before this node. ,

The third algorithm question is of medium difficulty in Leetcode, and its idea is roughly the same as the previous two algorithm questions. I will not copy the original question here, and the link above can directly jump to the question. Given a linked list, rotate the list and move each node of the list k positions to the right, where k is non-negative.

The length of the rotation can not exceed the length of the list, so the length of the rotation may exceed the length of the list.

  1. Calculates the length of the linked list
  2. What is the length of the rotation, using k % length;
  3. Use the method we described above to locate the nodes that need to be rotated.
  4. We get what we want.

The complete code is as follows:

 public ListNode rotateRight(ListNode head, int k) {
      if(head ==null||head.next ==null) {            return head; 
        }
        // Get the list length first.
 int nodeLength = 0;  ListNode d = head;  while(d ! =null) {  nodeLength++;  d = d.next;  }  // After getting the length, calculate how many nodes need to be moved.  int remaind =k % nodeLength ;  // If mid is equal to 0, there is no movement.  if (mid == 0) {  return head;  }  d = head;   // Let the fast pointer go remaind  for (int i = 0; i < remaind; i++) {  d = d.next;  }  ListNode temp = head;  // Record the previous node to which the slow pointer points  ListNode prev = null;  // Record the previous node to which the fast pointer points  ListNode tailPrev = null;  while(d ! =null) {  prev = temp;  tailPrev = d;  temp = temp.next;  d = d.next;  }  prev.next = null;  tailPrev.next = head;  return temp;  } Copy the code

In addition to the need to find the bottom first k nodes, but there is a class is also need to find the position of the specified node, the node is a special an intermediate node, we also need to use similar subject how Pointers can be solved, we make fast pointer take two steps at a time, every time we make slow pointer step, such as fast a pointer to the list at the end of The slow pointer points to the middle node of the list.

public static ListNode findMidNode(ListNode head) {
        ListNode fastNode = head;
        ListNode slowNode = head;
        ListNode prev = null;
        while(fastNode ! =null&& fastNode.next ! =null) {
 prev = slowNode;  fastNode = fastNode.next.next;  slowNode = slowNode.next;  }  return slowNode;  } Copy the code

1.2 Exercises

After reading the above, then take this problem to practice, the original problem is here: rearrange linked lists.

Given a single linked list L: L0→L1→… →L**n-1→Ln You can’t just change the values inside the nodes, but you need to actually switch nodes. Example 1: Given linked list 1->2->3->4, rearrange as 1->4->2->3. Example 2: Given linked list 1->2->3->4->5, rearrange as 1->5->2->4->3

First of all, LET me explain my idea. In fact, when we see this problem, we will find that in fact, this problem is to divide the linked list into two parts based on the midpoint of the linked list, and insert the last half of the linked list into the first half of the linked list one by one. In this case, we can use the template we mentioned above to get a two-part list, and once we get the two parts of the list, we can merge the two parts of the list. There is also a template for how to flip the second half of the list.

There are actually two ways to flip the linked list: one is on the original linked list, the other is using the data structure of stack. When the space complexity is O(1), we can’t use additional data structure, we can only use Pointers to operate the linked list and flip it.

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

The other way to do it is to use the stack, which is a little easier to write, so you can write it yourself. Below is the complete code for rearranging linked lists

public class Solution {  
 public void reorderList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
 // Find the middle node of the list  ListNode fast = head;  ListNode slow = head;  ListNode prev = null;  while(fast ! =null&& fast.next ! =null) {  prev = slow;  slow = slow.next;  fast = fast.next.next;  }  // Head is the first part of the list  prev.next = null;  // Slow is the last half of the list, which is reversed here. You can use stacks here.  ListNode listNode = reverseList(slow);   // Merge the two lists into one, you can create a new list, or you can do it directly on the head. But I didn't do a bad job of testing performance,  // Head can be a bit more complicated, requiring you to use several Pointers. If you are not familiar with it, you can create a new linked list.  // Use the stack is also possible, here you can try it yourself.  ListNode dummy = new ListNode(-1);  ListNode curr = dummy;  while(head ! =null&& listNode ! =null) { curr.next = head;  head = head.next;  curr.next.next = listNode;   listNode = listNode.next;  curr = curr.next.next;  }  // If the last part of the list is empty, we can know whether the list is odd or even.  // If the number of nodes is odd, the last half of the list will have one more node than the first half, because we count the middle node into the last half of the list.  if(listNode ! =null) { curr.next = listNode;  }  head = dummy.next;  }   public static ListNode reverseList(ListNode head) {  ListNode curr = head, prev = null;  ListNode temp;  while(curr ! =null) {  temp = curr.next;  curr.next = prev;  prev = curr;  curr = temp;  }  return prev;  } } Copy the code

2. Palindrome list && ring list type algorithm

Palindromic lists and circular lists are relatively simple topics. The judgment of palindrome linked list is just like what we said in the first section, using the fast and slow Pointers to find the position of the midpoint, and then comparing whether the latter half and the first half are in reverse order. Here we focus on the circular list of ideas.

2.1 Solution ideas and code templates

Check whether a linked list is a circular list

The first way we can think about it is we can use a hash table, and we can walk through the list, and if there’s a loop, there’s definitely going to be two visits to the same node.

 public static boolean hasCycle2(ListNode head) {
    HashSet set = new HashSet();
     while(head ! =null) {
         if (set.contains(head)) {
             return true;
 } else {  set.add(head);  }  head = head.next;  }  return false; } Copy the code

The solution with hash table is O(n) in time and O(n) in space. This method is the simplest and easiest to think of.

The second idea is to use fast and slow Pointers. The speed of the fast pointer is twice that of the slow pointer, so as to traverse the whole linked list. If there are rings in the single linked list, the two Pointers must meet at a certain node. The code is as follows:

public  boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while(fast ! =null&& fast.next ! =null) {
        fast = fast.next.next;
 slow = slow.next;  if (fast == slow) {  return true;  }  }  if (head == null || head.next == null) {  return false;  }  return false; } Copy the code

Return the first node of a linked list into a loop, or Null if there are no loops


If a singly linked list has a ring, two Pointers must meet at some point in the ring. When two Pointers meet, the slow pointer moves len + s1; The fast pointer goes len plus n times s1 plus s2, plus s1, because the fast pointer keeps going around the ring so it’s n times s1 plus s2. Since the speed of the fast pointer is twice that of the slow pointer, the length traveled in the same time must be the same, so the formula can be obtained: 2(len+S1) = len+ n(S1+S2)+S1. After simplification, the formula len = (n-1)S1 + nS2 is obtained. N is how many times the fast hand goes around the ring when the slow hand meets the fast hand. This equation is always true, so you can test it yourself. When we ignore the n variable, when we set n equal to 1, the formula becomes len equal to s2. So when the two Pointers meet, let the two Pointers start from node A and node C at the same time, and move one node each time. When they meet again, they will be the entry node of the circular linked list. The code is as follows:

public  ListNode hasCycle(ListNode head) {
    ListNode slow = head,fast = head;
    while(fast ! =null&& fast.next ! =null) {
        fast = fast.next.next;
        slow = slow.next;
 if (fast == slow) {  break;  }  }  if (fast == null || fast.next == null) return null;  fast = head;  while(fast ! = slow) { fast = fast.next;  slow = slow.next;  }  return fast; } Copy the code

3. List sorting && merge lists

Algorithm title:

  1. List order
  2. Merges two ordered lists
  3. Merge K ordered linked lists

3.1 Solution idea

The first algorithm, the linked list sorting and normal data sorting is the same way, because the list can’t random access nodes in the list, we can only by traversing the whole list, here the way we can use the merge sort of list is sorted, I believe you are quite familiar to merge sort, here we directly to the code.

To merge a list, the first thing we need to do is find the middle point of the list and divide it into two parts, and sort the two parts of the list. Then repeat the previous action for each part of the list until the end.

public static ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode fast = head.next, slow = head;
 while(fast ! =null&& fast.next ! =null) {  slow = slow.next;  fast = fast.next.next;  }  ListNode tmp = slow.next;  slow.next = null;  ListNode left = sortList(head);  ListNode right = sortList(tmp);  return merge(left, right) ; } // Merge the left and right parts private static ListNode merge(ListNode l1, ListNode l2) {  ListNode temp1 = l1, temp2 = l2;  ListNode dummy = new ListNode(-1);  ListNode prev = dummy;  while(temp1 ! =null&& temp2 ! =null) {  if (temp1.val > temp2.val) {  dummy.next = temp2;  temp2 = temp2.next;  } else {  dummy.next = temp1;  temp1 = temp1.next;  }  dummy = dummy.next;  } dummy.next = temp1 ! =null ? temp1 : temp2;  return prev.next; } Copy the code

In fact, merging two ordered lists is part of our first algorithm problem, and the code for merging two ordered lists can be directly used in the back part of the first algorithm problem. It is important to note that this method can only be used to merge two ordered lists

So how do you merge K ordered lists like problem number three? There are several ways to do this, such as:

1. Use the Java PriorityQueue PriorityQueue to implement, because the bottom of PriorityQueue is implemented using a binary heap, the smallest element is always at the top of the heap, so we can merge multiple ordered lists. But the important thing to note here is that we can only do this if multiple lists are ordered, but we can’t do this if we merge multiple unordered lists.

2. We can continue to use the idea of the second question. No matter how many linked lists are combined, we can combine them in pairs and finally summarize them into a linked list.

  1. Priority queue
public static ListNode mergeKLists(ListNode[] lists) {
    Queue<ListNode> pq = new PriorityQueue<>((v1,v2)->v1.val - v2.val);
    for (ListNode node : lists) {
        if(node ! =null) {
            pq.offer(node);
 }  }   ListNode dummyHead = new ListNode(-1);  ListNode tail = dummyHead;  while(! pq.isEmpty()) { ListNode minNode = pq.poll();  tail.next = minNode;  tail = minNode;  if(minNode.next ! =null) {  pq.offer(minNode.next);  }  }  return dummyHead.next; } Copy the code
  1. Two combined
public static ListNode mergeKLists2(ListNode[] lists) {
    if (lists == null || lists.length == 0) {
        return null;
    }
    return helper(lists, 0, lists.length - 1);
}  private static ListNode helper(ListNode[] lists, int begin, int end) {  if(begin==end) {  return lists[begin];  }  int mid = begin+(end-begin)/2;  ListNode left = helper(lists,begin,mid);  ListNode right = helper(lists,mid+1,end);  return merge(left,right); }  // Merge two ordered lists private static ListNode merge(ListNode l1, ListNode l2) {  ListNode temp1 = l1, temp2 = l2;  ListNode dummy = new ListNode(-1);  ListNode prev = dummy;  while(temp1 ! =null&& temp2 ! =null) {  if (temp1.val > temp2.val) {  dummy.next = temp2;  temp2 = temp2.next;  } else {  dummy.next = temp1;  temp1 = temp1.next;  }  dummy = dummy.next;  } dummy.next = temp1 ! =null ? temp1 : temp2;  return prev.next; } Copy the code

4. List switching types

  1. Flips the linked list for the specified node location
  2. Swap nodes in a linked list in pairs
  3. Flip linked lists in groups of K

There is no specific template for this type of problem, all you need to do is get a feel for how to solve it. Although there is no set template to follow, there are some key points that can be drawn. Step 1: We need to determine when we need to swap two nodes. Take the first algorithm problem above, the nodes that need to be swapped are the third to fifth nodes. Step 2: Then find the precursor and successor nodes that need to be swapped. So you can successfully move the node. Step 3: In this step, you need to determine how to move the pointer to satisfy your subsequent circular actions.


Let’s take the first algorithm problem for example. For easy understanding, we can refer to the animation above, and follow what we said above to see when we solve the problem.

Step 1: According to the meaning of the question, we find the node position to be swapped. Here they tell us that we need to swap the nodes between k — > n, and we don’t need to move the nodes beyond that. So here we need to determine whether the length of the list we’re walking through is between k and n.

Step 2: Find the precursor and successor nodes that need to swap nodes. Here I’m going through the list nodes between 3 and 5. Now that the location of the node to be changed is determined, find the precursor and successor nodes of the node to be changed, and use two Pointers preNode and nextNode to save the precursor and successor nodes. Then we swap the list to where we want it to go.

The third part: after we complete the node exchange, we also need to move the pointer we need to use accordingly.

The complete code is as follows:

public static ListNode reverseBetween(ListNode head, int m, int n) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode prev = dummy;
    int length = 0;
 ListNode temp;  while(head.next ! =null) {  length++;  // Find the condition that requires swapping nodes  if (length >= m && length < n) {  // Save the successor node of head  temp = head.next;  //head.next points to the successor node of the successor section  head.next = temp.next;  temp.next = prev.next;  prev.next = temp;  } else {  if (length < m) {  prev = prev.next;  }  head = head.next;  }  }  return dummy.next; } Copy the code

The second algorithm, two pairs of linked lists, which are actually very simple, the most important thing here is to control the position of the pointer to point to.

The third algorithm question is a difficult algorithm question in LeetCode. In fact, we will find that it is very easy to decompose the question regardless of the difficulty of the question. So they want K flipped lists, and K is less than the length of the list. In fact, flipping K lists one by one is no different from flipping a single list, except that we need to split K lists into groups for flipping, and then splice each flipped list together again.

public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(-1);
    dummy.next = head;
    ListNode pre = dummy;
    ListNode end = dummy;
 while(end.next ! =null) {  for (int i = 0; i < k && end ! =null; i++) {  end = end.next;  }  if (end == null) {  break;  }  ListNode start = pre.next;  ListNode next = end.next;  end.next = null;  pre.next = reverse(start);  start.next = next;  pre = start;  end = start;  }  return dummy.next; } public static ListNode reverse(ListNode head) {  ListNode curr = head, prev = null;  ListNode temp;  while(curr ! =null) {  temp = curr.next;  curr.next = prev;  prev = curr;  curr = temp;  }  return prev; } Copy the code

I will not list all the types one by one here. Most of the algorithm topics are similar, so I can roughly divide them into: Linked lists specify node operations, linked list sorting, circular linked list, linked list node swapping, linked list search and delete, linked list inversion, the idea is the same, but still need more practice, having ideas and being able to write are completely different things.

The last

I will not list all the types one by one here. Most of the algorithm topics are similar, so I can roughly divide them into: Linked lists specify node operations, linked list sorting, circular linked list, linked list node swapping, linked list search and delete, linked list inversion, the idea is the same, but still need more practice, having ideas and being able to write are completely different things.