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.

101. Reverse linked- List

The label

  • The list
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given the head node of a single linked list, reverse the list and return the reversed list.

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

Basic steps

So it looks something like this

null     [1|]-> [2|] -> [3|] -> null
  |(1)    |(2)    |(3)
prev     cur     cur.next
Copy the code

So let’s just think of it as 3 steps

  1. (3) 指向 (1)
  2. (1) (2) move back one
  3. Cur to null and then prev is the head of the list. Return it

Writing implement

This simple writing implementation is recommended as a memory module after understanding.

var reverseList = function(head) {
  let [cur, prev] = [head, null];
  while (cur) {
    [cur.next, prev, cur] = [prev, cur, cur.next]
  }
  return prev
};
Copy the code

102. Linked-list-cycle

The label

  • The list
  • simple

The title

Leetcode portal

Let’s just open leetCode.

Given a linked list, determine whether there are rings in the list.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. 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: POS is not passed as an argument, just to identify the actual state of the linked list.

Returns true if there are rings in the list. Otherwise, return false.

Input: head = [3,2,0,-4], pos = 1 output: true explanation: there is a ring in the linked list whose tail is connected to a second node.Copy the code

The basic idea

Idea 1: Markup

In the process of each walk, a Set or Array is used to record the address of the node visited. If there is a ring, there will always be repeated nodes. When the node to be walked falls in the Set, it indicates that there is a ring. Time complexity of O(n)

Idea 2: The speed pointer

Set the fast pointer to take two steps at a time and the slow pointer to take one step at a time. If there is a loop, the fast pointer will always catch up with the slow pointer in a certain round. O(n) time, you don’t need extra space O(1), constant memory

Writing implement

tag

const hasCycle = function(head) {
  const res = [];
  let cur = head;
  while (cur) {
    if (res.includes(cur)) {
      return true;
    }
    res.push(cur);
    cur = cur.next;
  }
  return false;
};
Copy the code

How fast a pointer

var hasCycle = function(head) {
  let [slow, fast] = [head, head]
  // If no loop is found, return false
  while(slow && fast && fast.next) {
    // The fast pointer takes two steps at a time and the slow pointer takes one step at a time
    fast = fast.next.next
    slow = slow.next
    // If you catch up, there is a ring
    if (fast === slow) {
      return true}}return false
};
Copy the code

Question: Why is it not possible to overtake fast === slow without a convergence?

There’s no such thing as one step at a time, one step at a time, two steps at a time, and you’ll see, if the fast pointer is behind the slow pointer, diff == 1 then the next time it will overlap. Diff is equal to 2, so if you take one more step, it becomes diff is equal to 1. Notice if you draw a picture on a piece of paper, you’ll see it immediately. I’m not going to draw it for you.

In addition to the set to increase the extra space to judge the way is not implemented, relatively simple.

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