This series is nothing fancy, just pure Leetcode problem breakdown analysis, not to use a sexy line or a niche solution, but with clear code and simple enough thinking to help you clarify the problem. Let you in the interview no longer afraid of algorithm written test.

103. Reverse-linked – list-II

The label

  • The list
  • medium

The title

Leetcode portal

Let’s just open leetCode.

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Note: Modification of a given linked list is not allowed.

Advanced: Can you solve this problem using O(1) space?

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

The basic idea

According to the previous problem – circular linked list we know two ways, this problem is actually the same idea, but not a variant, requiring input and output link point.

Similarly, we can have two thought markers and a fast or slow pointer.

The label is too simple to mention

The derivation of the fast and slow pointer

In fact, the main thing we know about an implicit equation is that the total length of a fast pointer is 2: 1 at any time

In this way: the purple point is the confluence point, the fast pointer has completed n cycles of the ring, and the total length of the fast pointer to the confluence can be expressed as a + n(b+ C) + b

The length of the slow pointer to the convergence is a + b, so the fast pointer implies the relationship between the two cups can be expressed as 2(a + b).

So we have the equation a plus n times b plus c plus b is equal to 2 times a plus b, and notice we’re dealing with the A entry

I’m not going to write this down so a is equal to c plus n minus 1 times b plus c, or I could use a special way, let’s say n is equal to 1, so a is equal to c and notice that b plus c is going all the way around, back to the origin

Writing implement

tag

Mark the same as the last time. When you find the same node the second time, it indicates that the node is the ring entrance.

var detectCycle = function(head) {
    // This time we use set
    const visited = new Set(a)let cur = head;
    while(cur) {
      // Find the second time, it is the entrance
      if (visited.has(cur)) {
        return cur
      }
      visited.add(cur)
      cur = cur.next
    }
    return null
};
Copy the code

Very simple idea, but order n in space.

How fast a pointer

var detectCycle = function(head) {
    let [slow, fast, preOther] = [head, head, head];
    while(slow && fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            // Add a new node to start from scratch when preOther === slow is the entry point
            while(preOther ! == slow) { slow = slow.next; preOther = preOther.next; }return preOther
        }
    }
    return null
};
Copy the code

So the space complexity O(1)

104. Reverse-nodess-in-k-group (reverse-Nodess-in-K-group)

The label

  • The list
  • difficult

The title

Leetcode portal

Let’s just open leetCode.

You are given a linked list, each k nodes in a group of flipped, please return to the flipped list.

K is a positive integer whose value is less than or equal to the length of the list.

If the total number of nodes is not an integer multiple of k, keep the last remaining nodes in the same order.

Advancements: Can you design an algorithm that only uses constant extra space to solve this problem? You can’t just change the values inside the nodes, you need to actually swap nodes.

Case 1

Input: head = [1,2,3,4,5], k = 2 output: [2,1,4,3,5]Copy the code

Case 2

Input: head = [1,2,3,4,5], k = 3 output: [3,2,1,4,5]Copy the code

The basic idea

We should be good at breaking down big problems into small, simple ones.

A group of K flipped lists split into

  • How to group
  • How to turn over

And that brings us to the previous problem — flipping lists. Is the subproblem in this question, but because of the need to record the length, a little modification.

As for grouping by k, you can use a counter and do the following flip every time you fill up to k. Then go recursively to the next number of rounds of the flipped list and connect. The key is drawing on paper.

Writing implement

var reverseKGroup = function(head, k) {
  let count = 0, cur = head;
  // Get k nodes of this round (maybe not enough)
  while(cur ! =null&& count ! == k){ cur = cur.next; count++; }// This round is full of k and needs to be flipped
  if (count === k) {
    // Recursively link the following k reverse list head nodes
    cur = reverseKGroup(cur, k)
    while(count ! =0) {
      // This loop is flipped
      [head.next, cur, head] = [cur, head, head.next]
      count--;
    }
    head = cur
  }
  return head
};
Copy the code

Next, cur, head] = [cur, head, head.next]

Assume that k = 3 | [1] - > [2 |] - > [3 |] - > | [4] - > null count 0 1 2 3 | | head curCopy the code

Start flipping step 1 head. Next = cur

       [1|]   ->   [2|]   ->   [3|]   ->   [4|] -> null
         |                                  ^
         |__________________________________|

Copy the code

Step 2 cur = head

       [1|]   ->   [2|]   ->   [3|]   ->   [4|] -> null
         |                                  ^
         |__________________________________|
        |
       cur
       head
Copy the code

Step 2 head = head. Next

| | [1] - > [2] - > [3 |] - > - > null | | [4] ^ | __________________________________ | | | cur head count = 2 at this timeCopy the code

[head. Next, cur, head] = [cur, head, head. Next

| | [1] < - [2] - > [3 |] - > - > null | | [4] ^ ^ ^ | __________ | ___________ | ____________ hold | | | cur head count = 1 at this timeCopy the code

[cur, head, head] = [cur, head, head

| | [1] < - [2] < -- - > | [3] [4 |] - > null | ^ ^ | ______________________ | ____________ hold | | | cur head count = 0 at this timeCopy the code

Head = cur


       [1|]  <--   [2|]   <--  [3|]      [4|] -> null
         |                      ^          ^
         |______________________|__________|
                                |           
                               head         
Copy the code

Does that make sense

In addition, we recommend this series of articles, very simple, on the front of the advanced students are very effective, wall crack recommended!! Core concepts and algorithm disassembly series

If you want to brush the questions with me, you can add me on wechat. Click here to make a friend Or search my wechat account, infinity_9368. You can chat with me and add my secret code “Tianwang Gaidihu”. Verify the message please send me Presious tower shock the rever Monster, I see it through, after adding I will do my best to help you, but pay attention to the way of asking questions, it is suggested to read this article: the wisdom of asking questions

reference