Let’s take a look at the five problems THAT I’ve done today, and again, the solution may not be optimal, it’s all in my head

Solution, if you have a better solution, I hope you can freely advise. Thanks in advance.

The first question

Sword refers to Offer II 024. Reverse linked list

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

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

So this is trying to reverse a linked list, and since we know that linked lists can’t reverse arrays, when we get a 1

Hou, only know next. Val = 2, we want to achieve is to make 2 – > 1, then the 3-2, but we direct 2. Next = 1,

We’re not going to be able to get to 3, because the chain that goes from 2 to 3 is already broken, so we’re going to be able to get to 2 to 3 as well as 2 to 1. At this moment

By now I think you’ve all figured out that instead of changing the pointer on the original list, we can create a new list and put the original chain one at a time

If we want to get to 3, we need head = head. Next,

So we’ve got the next list, so what do we do if we reverse the list.

/** * @param {ListNode} head * @return {ListNode} */ var reverseList = function (head) { while (head ! = null) {next let next = head.next; Head. Next = link; // Separate the current first and link its next to the new list. // Copy this to the target list link = head; // recycle to get the next bit, fetch, place the target on its next, copy and fetch head = next; } return link; };Copy the code

Since I don’t know how to draw yet, I’m going to write out everything I can in terms of flow

First loop head 2->3->4->5-> NULL link 1-> NULL Second loop head 3->4->5-> NULL link 2->1-> NULL......Copy the code

This completes a linked list loop

The second question

Interview question 02.07. Linked lists intersect

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If the two

The linked list has no intersections, return NULL.

The two linked lists intersect at node C1:

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 output: Intersected at '8' The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.Copy the code

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 output: Intersected at '2' The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.Copy the code

I started out with the idea of finding the first equal value of two lists, so I looping through two lists to compare val, and then

I realized it wasn’t as simple as I thought, and I was looking for exactly the same thing back there. I figured I’d flip the two lists, and

Find the last one that’s equal, take the first one, and reverse it back, but it says you can’t change the original structure of the list, and

And this idea is difficult to realize, and the time complexity of the table, and finally honest one by one to the back row, you can chain the list

The ones that are the same length can be compared like this, and what if the ones that are not the same, what do we do? Since the lengths are not equal, let’s make it phase

Just wait, that’s a plus b is equal to b plus a, so if I put the two lists together, they’ll be the same length.

And there you have it

/** * @param {ListNode} headA * @param {ListNode} headB * @return {ListNode} */ var getIntersectionNode = function(headA, headB) { let a = headA; let b = headB; while (a ! == b) {// If either a or B ends, then spell a = a == null? headB : a.next; b = b == null ? headA : b.next; } return a }; Such as: a = 0 and 1 > > 9 - > 2 - > 4 b = 3 - > 2 - > 4 a + b = 0-9 - > > > 1, 4 - > 2 - > 3 - > 2 - > 4 b + a = 4 - > 2 - > 3 - > 0 and 1 > > 9 - > 2 - > 4Copy the code

We always get what we want in the end. What’s wrong with that, guys?

The third question

703. The k-th large element in the data stream

Design a class that finds the KTH largest element in the data stream. Notice it’s the KTH largest element, not the KTH different element

Elements.

Please implement KthLargest class:

• KthLargest(int k, int[] nums) uses the integer k and the integer stream nums to initialize the object.

• Int add(int val) Returns the KTH largest element in the current data stream after inserting val into the data stream nums.

  Input: [” KthLargest “, “add”, “add”, “add”, “add”, “add”] [[3] [4, 5, 8, 2], [3], [5], [10], [9], [4]] output: [null, 4, 5, 5, 8, 8]

  KthLargest KthLargest = New KthLargest(3, [4, 5, 8, 2]); kthLargest.add(3); // return 4 kthLargest.add(5); // return 5 kthLargest.add(10); // return 5 kthLargest.add(9); // return 8 kthLargest.add(4); // return 8

To be reasonable, this is my first time to do this kind of problem, I looked at the problem for ten minutes, I did not understand what this is, I know every word, but even

Once I a Chinese score is not low, unexpectedly did not know what it is about. After my unremitting efforts, I finally read

Understand the problem dry.

Translation is that adult words [[3, 4, 5, 8, 2]], [3], [5], [10], [9], [4]], it [3, [4, 5, 8, 2]] is I want to find 3 big 3

Element, where do I find it, the initial array is [4, 5, 8, 2], we can understand that, this is 5, very simple, so what does it mean, this array is going to keep adding to it, [3], [5], [10], [9], [4], that’s what I’m adding every time, ratio

If the first 3 is added, the third largest element is returned. And then we add another 5, and then we return the first

Three big elements.

So now we’re starting to think about how to implement it, and it’s a lot easier to implement it, sort the array from the largest to the smallest, and then go in, okay

I’m just going to put the next number in where I’m going to put it, and I’m just going to go back and forth and look for the element that I need to find, but I tried, in

LeetCode takes a lot of time, it takes a lot of time, so I’m using sort, so the only thing that can shorten the time is interpolation

It’s time to add a new element, so I used the rule of two

/** * @param {number} k * @param {number[]} nums */ var KthLargest = function (k, nums) { this.k = k this.nums = nums.sort((a, b) => b - a); }; /** * @param {number} val * @return {number} */ KthLargest.prototype.add = function (val) { let low = 0; let high = this.nums.length-1; While (high >= low){const mid = math.floor ((low + high) / 2) const v = this.nums[mid] // Determine what part of the new value is in, If (v==val){this.nums.splice(mid, 0); If (val>v){high = mid-1}else{low = mid+1}} if(low>high){this.nums.splice(low, 0, 0) Return this.nums[this.k - 1]};Copy the code

This is certainly not the optimal solution, but it is the best solution I can come up with independently, if there is a better way, I hope friends can propose

Correct me. I’m stupid. If you can teach me, you must be very good.

The fourth question

226. Flip the binary tree

Input 4 / \ 2 7 / \ / \ 1 3 6 9 Output 4 / \ 7 2 / \ / / 9 6 3 1Copy the code

See this topic stem more easy to understand, according to our northeast speak, this doesn’t drop a son yao, this has what difficult.

Simply, a recursion.

Var invertTree = function(root) {if (root==null) return null; InvertTree (root.left) let right = invertTree(root.left) invertTree(root.left) let right = invertTree(root.right // Return root};Copy the code

InvertTree (root. Left) invertTree(root. Left) invertTree(root.

Root.right), otherwise, the first time it is inverted, the second time it is inverted, then it is back again.

The fifth problem

61. Rotate linked lists

To give you the head of a linked list, rotate the list and move each node to the right by k **.

This topic is reasonable, I see the word or did not understand, but there is a figure, this figure is clear at a glance and chest. It’s a linked list in front, and a linked list in back

The face is the number of times the last bit of the list moves to the first. What am I supposed to do, take the last one out and put it first? I

After thinking for a long time, the last one is easy to take out, but how can I get the first four without the last one, it stumped me. In order to

My store of knowledge. I’ve tried for hours, and I’ve failed. But, if it’s so hard to put the last one forward, why don’t I

So let’s put the first one to the end, and at first I thought, well, let me go through it once, find the length, and then I’ll put the first one again and again

And then finally, let’s say 1→2→3→4→5, k=2, length len=5, and I’ll just put the first one to the end three times, but,

So I’m going to have to take the first one three times, and then I’m going to put it at the end, and then I’m going to loop back to the last one

And then you have to save the original head, otherwise you can’t find it. Oh, my God, what a hassle.

So, since I thought of putting the first one to the last one, why don’t I just join them together, make a circular linked list,

So I don’t have to take them away and add them in. Just cut it off where it needs to be. This problem will be solved

The decision yet. But there’s another question, if my list is not as long as K, do I have to count the number of times,

I can run a circle, I do not turn the number of linked list, since the middle of the full circle is redundant query, that we only want to check less than a circle.

/** * @param {ListNode} head * @param {number} k * @return {ListNode} */ var rotateRight = function(head, K) {/ / null value judgment if (head = = null | | head. The next = = null | | k = = 0) return the head / / or archived a let the link = head let n = 1; While (link.next) {n++ link = link.next} // Let len = n-k % n // If it is exactly the whole number of laps, that's great, We don't have to do anything if (len == n) return head; Link. next = head // Where we want to go, While (len) {link = link.next len--} const res = link.next Next = null return res};Copy the code

In this way, say difficult, say simple I also did for a long time to finish. The solution of these five problems must be not perfect, but I did it all by myself. I have a great sense of achievement. It’s already 2:30 in the morning, and I’m tired to death. We’d better not stay up late, let’s work together!