Algorithm Supplements Fifteen Complementary Linked List Related Interview Questions

判断链表是否相交

给定两个可能有环也可能无环的单链表,头节点head1和head2.请实现一个函数,如果两个链表相交,请返回相交的 第一个节点.如果不相交,返回null
【要求】 如果两个链表长度之和为N,时间复杂度请达到O(N),额外空间复杂度 请达到O(1).
思路：
First solve the problem of cyclic and acyclic：If there is no loop return null,If there is a loop return the first incoming node.
The frame below is the first entry point：

First, solve this problem through the container method,准备一个HashSetkeep all passing nodes,Judge every time you pass a node
是否存在于HashSet里面.
Next, go deep into the method without the container（The key is how to find the first entry point）：准备一个快指针（一次走两步）and a slow pointer（一次走一步）,If the fast pointer goes to empty early,Then it must be an acyclic singly linked list,Then the fast and slow pointers will definitely meet,
When met after the pointer to the node,The pointer and then slow and fast pointer step every time,The location of the encounter is the first entry point.

On the above pointsS与F相遇了（S代表慢指针,F代表快指针）.
接下来F回到开头,become one step at a time

S和Ftake two steps,The point of encounter is the first entry point.

Similarly, the following boundary conditions are also establishedF回到头节点,而Sthen loops on that loop point

代码如下：

	// 找到链表第一个入环节点,如果无环,返回null
	public static Node getLoopNode(Node head) {
    
		//Determine in advance whether there are three points
		if (head == null || head.next == null || head.next.next == null) {
    
			return null;
		}
		// n1 慢 n2 快
		Node slow = head.next; // n1 -> slow
		Node fast = head.next.next; // n2 -> fast
		//If the fast and slow pointers do not meet, keep looping
		while (slow != fast) {
    
			if (fast.next == null || fast.next.next == null) {
    
				return null;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		// slow fast 相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
    
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

Next, find the first entry node of the two linked lists（loop1和loop2）
1、如果都为空,Then consider how to judge the intersection of two acyclic singly linked lists（类似于Y）
Use if you have a containerhashSetGet the memory address of the corresponding node
Integer.toHexString(obj.hashCode())
如果没有容器,从链表1Find the first setend1,find lengthlen1
从链表2出发找到end2,如果end1的内存地址和end2的内存地址不相等,then this linked list
肯定不相交【end1和end2is the last node of the intersection】
So how to find the first node of the intersection?？
方式：
如果链表1是100个节点,链表2是80个节点,Let the linked list first1先迈20步,Then let the linked list1和链表2
一起走,then they must meet at the first intersecting node（因为endIt's all the same but the length is different）
代码如下：

	// 如果两个链表都无环,返回第一个相交节点,如果不想交,返回null
	public static Node noLoop(Node head1, Node head2) {
    
		if (head1 == null || head2 == null) {
    
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		//如果npositive linked list1长,负数链表2长
		while (cur1.next != null) {
    
			n++;
			cur1 = cur1.next;
		}
		while (cur2.next != null) {
    
			n--;
			cur2 = cur2.next;
		}
		//Disjoint if memory addresses are different
		if (cur1 != cur2) {
    
			return null;
		}
		// n : 链表1长度减去链表2长度的值
		cur1 = n > 0 ? head1 : head2; // 谁长,谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短,谁的头变成cur2
		//cur1Save the head of a long linked list,cur2Save the head of the short list
		n = Math.abs(n);
		while (n != 0) {
    
			n--;
			//Then let the long linked list move backwardsn步
			cur1 = cur1.next;
		}
		//Long linked list and short linked list go together,直到相遇
		while (cur1 != cur2) {
    
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

2、Divided into a linked list with a cycle and a linked list without a cycle
注：这种情况不可能相交（Because the intersection will definitely cause the two linked lists to form a ring）,如果一个链表不成环
If so, then it's definitely not intersecting.

3、两个链表都有环（loop1和loop2都不为空）
（1）The two rings are independently disjoint

（2）统一理解为head1和head2入环节点是同一个
（3）Here the link point is not the same

Thus it can be concluded that ifloop1等于loop2is the second case,But how to ask for a relationship?,则可以
Consider the two linked lists asloop1和loop2结尾,Then find the intersection of two acyclic linked lists.
如果loop1不等于loop2,Is either1either situation3,则从loop1Start walking around and see if you can
loop2相遇,If you meet, it's the situation3,If there is no encounter then it is the situation1.
代码如下：

// 两个有环链表,返回第一个相交节点,如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    
		Node cur1 = null;
		Node cur2 = null;
		//情况2,Same as the previous acyclic linked list intersection
		if (loop1 == loop2) {
    
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
    
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
    
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n);
			while (n != 0) {
    
				n--;
				cur1 = cur1.next;
			}
			while (cur1 != cur2) {
    
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {
    
			//情况1或者情况3
			cur1 = loop1.next;
			//loop1Start to cycle down,If found during the first looploop2了,
			//then return the current point of intersection,If the first loop is over then there is no intersection to returnnull
			while (cur1 != loop1) {
    
				if (cur1 == loop2) {
    
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

整体代码如下：

	public static class Node {
    
		public int value;
		public Node next;

		public Node(int data) {
    
			this.value = data;
		}
	}

	public static Node getIntersectNode(Node head1, Node head2) {
    
		if (head1 == null || head2 == null) {
    
			return null;
		}
		Node loop1 = getLoopNode(head1);
		Node loop2 = getLoopNode(head2);
		if (loop1 == null && loop2 == null) {
    
			return noLoop(head1, head2);
		}
		if (loop1 != null && loop2 != null) {
    
			return bothLoop(head1, loop1, head2, loop2);
		}
		return null;
	}

	// 找到链表第一个入环节点,如果无环,返回null
	public static Node getLoopNode(Node head) {
    
		//Determine in advance whether there are three points
		if (head == null || head.next == null || head.next.next == null) {
    
			return null;
		}
		// n1 慢 n2 快
		Node slow = head.next; // n1 -> slow
		Node fast = head.next.next; // n2 -> fast
		//If the fast and slow pointers do not meet, keep looping
		while (slow != fast) {
    
			if (fast.next == null || fast.next.next == null) {
    
				return null;
			}
			fast = fast.next.next;
			slow = slow.next;
		}
		// slow fast 相遇
		fast = head; // n2 -> walk again from head
		while (slow != fast) {
    
			slow = slow.next;
			fast = fast.next;
		}
		return slow;
	}

	// 如果两个链表都无环,返回第一个相交节点,如果不想交,返回null
	public static Node noLoop(Node head1, Node head2) {
    
		if (head1 == null || head2 == null) {
    
			return null;
		}
		Node cur1 = head1;
		Node cur2 = head2;
		int n = 0;
		//如果npositive linked list1长,负数链表2长
		while (cur1.next != null) {
    
			n++;
			cur1 = cur1.next;
		}
		while (cur2.next != null) {
    
			n--;
			cur2 = cur2.next;
		}
		//Disjoint if memory addresses are different
		if (cur1 != cur2) {
    
			return null;
		}
		// n : 链表1长度减去链表2长度的值
		cur1 = n > 0 ? head1 : head2; // 谁长,谁的头变成cur1
		cur2 = cur1 == head1 ? head2 : head1; // 谁短,谁的头变成cur2
		//cur1Save the head of a long linked list,cur2Save the head of the short list
		n = Math.abs(n);
		while (n != 0) {
    
			n--;
			//Then let the long linked list move backwardsn步
			cur1 = cur1.next;
		}
		//Long linked list and short linked list go together,直到相遇
		while (cur1 != cur2) {
    
			cur1 = cur1.next;
			cur2 = cur2.next;
		}
		return cur1;
	}

	// 两个有环链表,返回第一个相交节点,如果不想交返回null
	public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
    
		Node cur1 = null;
		Node cur2 = null;
		//情况2,Same as the previous acyclic linked list intersection
		if (loop1 == loop2) {
    
			cur1 = head1;
			cur2 = head2;
			int n = 0;
			while (cur1 != loop1) {
    
				n++;
				cur1 = cur1.next;
			}
			while (cur2 != loop2) {
    
				n--;
				cur2 = cur2.next;
			}
			cur1 = n > 0 ? head1 : head2;
			cur2 = cur1 == head1 ? head2 : head1;
			n = Math.abs(n);
			while (n != 0) {
    
				n--;
				cur1 = cur1.next;
			}
			while (cur1 != cur2) {
    
				cur1 = cur1.next;
				cur2 = cur2.next;
			}
			return cur1;
		} else {
    
			//情况1或者情况3
			cur1 = loop1.next;
			//loop1Start to cycle down,If found during the first looploop2了,
			//then return the current point of intersection,If the first loop is over then there is no intersection to returnnull
			while (cur1 != loop1) {
    
				if (cur1 == loop2) {
    
					return loop1;
				}
				cur1 = cur1.next;
			}
			return null;
		}
	}

总结

能不能不给单链表的头节点,只给想要删除的节点,就能做到在链表上把这个点删掉?
The smart way：give the node to delete,把该节点的next赋值给该节点,Then let the node across the next node,让nextPointer to down a node actually such did not remove himself in nature,除此之外,The tail node cannot be deleted