This is the 12th day of my participation in the August More Text Challenge. For details, see:August is more challenging

Topic link

160. Intersecting linked lists

Topic describes

Given the head nodes headA and headB of two singly linked lists, you find and return the starting node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

In the figure, two linked lists intersect at node C1:

The topic data guarantees that there are no rings in the entire chain structure.

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

The test case

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 The intersecting node has a value of 8 (note that it cannot be 0 if two linked lists intersect). Starting from their respective table heads, list A is [4,1,8,4,5] and list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersection node; In B, there are three nodes before the intersection node. Note: If it does not intersect, null is returned; If it intersects, return the first node that intersectsCopy the code

Tip:

  • The number of nodes in listA is M
  • The number of nodes in listB is n
  • 0 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • If listA and listB do not intersect, intersectVal is 0
  • If you have any intersection, listA and by intersectVal = = listA = = [skipA + 1] by [skipB + 1]

Subject analysis

Two linked lists, to judge the intersection, if the array is used to store each of their nodes, we start from the end of the comparison, we can know whether the intersection, if the intersection is like a node (who let this list is one-way ┑(￣ ε ￣)┍)

Tries to answer

Let’s just say it barely made it out, and it didn’t work very well

Need to convert the list into an array, need to take up the operation time, the operation generated after the array, take up additional control space

var getIntersectionNode = function(headA, headB) {
	let a = [],
		b = [];
	while(headA ! =null) {
		a.unshift(headA);
		headA = headA.next;
	}
	while(headB ! =null) {
		b.unshift(headB);
		headB = headB.next;
	}
	if (a.length == 0 || b.length == 0 || a[0] != b[0]) return null;
	let n;
	for (; a[0] == b[0] && a[0] != null; a.shift(), b.shift()) {
		n = a[0];
	}
	return n;
};
Copy the code

Optimize the summary

Conclusion first, hash YYds

The first list is converted into a hash structure, and then the second list is traversed to determine the existence of elements with the help of the excellent hash mechanism

The performance is slightly better than the last one, but the memory usage is less than half! After all, there is only one extra Set to store data

var getIntersectionNode = function(headA, headB) {
	if (headA == null | headB == null) return null;
	let a = new Set(a);while(headA ! =null) {
		a.add(headA)
		headA = headA.next;
	}
	let node = null;
	while(headB ! =null) {
		if (a.has(headB)) {
			node = headB;
			break;
		}
		headB = headB.next;
	}
	return node;
};

Copy the code

An interesting solution

Was mentioned, the two lists is common items, in fact, the biggest difficulty is the length of two lists do not correspond, can’t at the same time the head = head. Next to compare nodes, so directly to traverse the two list, get length n, m, and then let the longest that list first step forward | | n – m, Now both lists can move forward in sync

Official best double pointer problem solution

Based on the idea of the last problem, let the two lists of the same length, that can not go back from the beginning at the same time?

So, if we make both lists a plus b, b plus a, by counting them extra, then we can go backwards at the same time? With only two Pointers and two flags, no additional space is needed for data storage

The idea is that the pa pointer first traverses the a list, and when the A list traverses, changes the flagA flag, and then traverses the B list, and ends

The PB pointer first iterates over B, and when it’s done, it changes flagB and turns its head over the A list until it’s done

var getIntersectionNode = function(headA, headB) {
	let flaga = true,
            flagb = true;
	for (leta = headA, b = headB; a ! =null|| b ! =null; a = a.next, b = b.next) {
		if (a == null && flaga) {
			a = headB;
			flaga = false;
		}
		if (b == null && flagb) {
			b = headA;
			flagb = false;
		}
		if (a == b) {
			returna; }}return null;
};

Copy the code

The last piece of code looked pretty straightforward, but it was a little verbose

Think about it a lot, tweak it a little bit, change the types of tags, integrate the judgment into the for

var getIntersectionNode = function(headA, headB) {
	let n = 1,
            m = 1;
	for (leta = headA, b = headB; a ! =null|| b ! =null; 
            a = a.next || (n-- > 0 ? headB : null),
            b = b.next || (m-- > 0 ? headA : null)) {
		if (a == b) {
			returna; }}return null;
};

Copy the code

I think the most excellent design is to use this version to | | circuit function, although each loop has, but in fact is executed 2 times