Hello everyone, this official account will be restored to update. The last update was in 2016, four years ago.
In the past 4 years, I have experienced a lot of things in work and life, such as job-hopping, changing direction and changing industries. She had married, had a baby, bought a house and settled down. Finally, I stayed in The city of Beijing. I seem to be so busy every day that I forget I wrote pressure and Time.
This year has been the most difficult employment season in the world due to the pandemic. At this time to restore the update also hope to find a job for everyone small partners have a little help, even if a little.
In addition, the following articles may not only be limited to algorithm questions, but also have engineering problems and practices encountered in the work, which is a kind of summary. – Elasticsearch should come first
The first common node of the two linked lists is the subject of Easy in LeetCode, and the Acceptance reaches 63.8%. The title is as follows:
Enter two linked lists to find their first common node. Here are two linked lists:
The intersection begins at node C1. Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Reference of the node with value = 8 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.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2 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.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 output: null From their respective headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.
Note:
If two lists do not intersect, null is returned.
After the result is returned, both lists must remain in their original structure
It can be assumed that there are no loops in the entire list structure. The program meets the O(n) time complexity as far as possible and uses only O(1) memory. Question 160 is the same as that in the main station: leetcode-cn.com/problems/in… Source: LeetCode link: leetcode-cn.com/problems/li…
Here’s the idea:
There is a prerequisite for this problem, which is that two lists must have common nodes. To determine that two lists intersect, that’s another question.
Of course, it is easy to only determine whether the link intersects. As long as two linked lists traverse to the end node respectively, it is ok to judge whether the nodes are the same (the premise is that the linked list has no rings).
If it intersects, how do you find out which node it intersects at? Here’s the idea. First of all, linked lists can only be accessed sequentially, not randomly. That’s the premise. In this case, the only way to solve the problem is to traverse the list.
We use two Pointers: node1, node2 points to the headA and headB of the two lists, and then go through each node at the same time. When node1 reaches the tail of headA, it is repositioned to the head of headB. When node2 reaches the end of linked list headB, it is relocated to the head of linked list headA.
So when they meet, the node they point to is the first common node.
For example, as shown in Figure 1 below, node1 and node2 point to headA and headB of the two linked lists respectively. When node1 reaches the tail node, Node2 is the node before the tail node (node 4), as shown in Figure 2. Next, node1 points to the head of list B, at which point Node2 reaches the tail node 5, as shown in Figure 3. Continuing, node1 points to 0 and node2 points to 4, the head of linked list A, as shown in Figure 4. At this point we find that node1, Node2 are the same distance to the first public node, and if we continue walking, we will definitely meet at the first node.
Clear thinking, the code is as follows: Java version
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) returnnull; ListNode L = headA; ListNode R = headB; int count=0; // when a node reaches the end of a list, it continues from another list, with count++while(L ! = R) { L = L.next; R = R.next;if (L == null) {
L = headB;
count ++;
}
if (R == null) {
R = headA;
count++;
}
if (count >2) {
returnnull; }}return L;
}
Copy the code
Finally, in addition to the algorithm questions, which interview questions you want to see can leave a message to me, back-end engineering, algorithm, mathematical formula derivation can be. I don’t know how to make a fool of myself.
If you think the article is helpful, you might as well pay attention to this public number, of course, also hope to help the author to promote, more people pay attention to me will be more motivated, thank you in advance.
