date: 2016-08-18 9:15:00
title: 数据结构之链表面试题汇总（四）得到两个单链表相交的第一个交点、用O（1）的时间效率删除单向链表中的指定节点
categories: 数据结构
版权声明：本站采用开放的[知识共享署名-非商业性使用-相同方式共享 许可协议]进行许可
所有文章出现的代码，将会出现在我的github中，名字可以根据类全名来找，我在github中的文件夹也会加目录备注。
得到两个单链表相交的第一个交点
思路：
- 要得到两个单链表相交的第一个交点，首先得判断这两个单链表有没有相交
- 而判断两个单链表是否相交，就要判断两个单链表的最后一个节点是否电箱
- 只有两个链表的最后一个节点相等，两个链表才可能相交。
- 同时还需要考虑两个单链表长度的问题，既然两个链表相交是相交之后那部分的节点一样，那么我们可以把较长链表前面那部分截成跟较短链表长度一样，然后再找相交节点
图解：
代码实现：
public class FirstIntersectNode {
public static Node getFirstIntersectNode(Node head1, Node head2) {
// judge head1 and head2 wether is null,if true return null
if (head1 == null || head2 == null)
return null;
// use 2 variables to record their length
int length1 = 0;
int length2 = 0;
// compare them move longer one to the equal length
Node current1 = head1;
Node current2 = head2;
Node last1 = head1;
Node last2 = head2;
// get these lists's length and the tail node
while (last1.getNext() != null) {
length1++;
last1 = last1.getNext();
}
while (last2.getNext() != null) {
length2++;
last2 = last2.getNext();
}
// if their last node unequal that they have no intersection
if (last1 != last2) {
return null;
}
// set their length to equal
if (length1 > length2) {
int k = length1 - length2;
while (k != 0) {
current1.getNext();
k--;
}
} else {
int k = length2 - length1;
while (k != 0) {
current2.getNext();
k--;
}
}
// while the current node is not the last node
while (current1 != null) {
// move these pointers together backward in one step
current1 = current1.getNext();
current2 = current2.getNext();
if (current1 == current2) {
// compare the two current node if equal return node
return current1;
}
}
return null;
}
}
测试代码:
public class ReverseLinkedListTest {
/**
* @param args
*/
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
Node list1 = new Node(23);
Node list2 = new Node(23);
Node list3 = new Node(2);
Node list4 = node4;
Node list5 = node5;
list1.setNext(list2);
list2.setNext(list3);
list3.setNext(list4);
list4.setNext(list5);
System.out.println(FirstIntersectNode.getFirstIntersectNode(node1,
list1).getRecord());
}
}
运行结果：
测试代码:不相交的两条链表
public class ReverseLinkedListTest {
/**
* @param args
*/
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
Node list1 = new Node(23);
Node list2 = new Node(23);
Node list3 = new Node(2);
Node list4 = new Node(2);
Node list5 = new Node(2);
list1.setNext(list2);
list2.setNext(list3);
list3.setNext(list4);
list4.setNext(list5);
System.out.println(FirstIntersectNode.getFirstIntersectNode(node1,
list1).getRecord());
}
}
运行结果：
用O（1）的时间效率删除单向链表中的指定节点
思路：
用O（1）的时间效率删除单向链表中指定节点，猛然一看好像不可能，因为单向链表是线性的，既然要删除指定的节点，必须要对整个链表进行遍历。
再仔细想想，好像也不一定需要遍历整条链表，有没有考虑过需要遍历整条链表的情况？那是最坏的情况吧？即要删除的节点在指定链表的最后一个节点，这时就需要遍历整条链表，得到最后一个节点的前一个节点，然后设置前一个节点的后面节点为空
可是整条链表前n-1个元素，都可以直接通过设置当前节点的值和指向下一个节点的引用，即通过把下一个节点的值赋给当前节点的值，把下一个节点的下一个节点的指向，赋给当前节点的下一个节点指向即可
这样删除的时间复杂度为 前n-1个元素为O（1），最后一个为O（n) 但是总的来说 (n-1)*O(1)+O(n)]/n=O(1)
图解：
代码实现：
public class O1DeleteNode {
public static void deleteNode(Node head, Node targetNode) {
// judge head and tnode if they are null throw ex
if (head == null || targetNode == null)
throw new RuntimeException("the head or tnode is null");
// judge tnode is the last node get the front node and set its next null
if (targetNode.getNext() == null) {
Node current = head;
while (current.getNext() != targetNode) {
current = current.getNext();
}
current.setNext(null);
} else {
// else directely assign the next value to tnode and next to tnode
targetNode.setRecord(targetNode.getNext().getRecord());
targetNode.setNext(targetNode.getNext().getNext());
}
}
}
测试代码：情况一：非末尾节点:
public class ReverseLinkedListTest {
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
RecustionAllElementOfLinkedList.printAllElements(node1);
System.out.println("----------------------------------------------");
O1DeleteNode.deleteNode(node1, node4);
System.out.println("----------------------------------------------");
RecustionAllElementOfLinkedList.printAllElements(node1);
}
}
运行结果：
测试代码：情况二：删除末尾节点：
public class ReverseLinkedListTest {
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
node1.setNext(node2);
node2.setNext(node3);
node3.setNext(node4);
node4.setNext(node5);
RecustionAllElementOfLinkedList.printAllElements(node1);
System.out.println("----------------------------------------------");
O1DeleteNode.deleteNode(node1, node5);
System.out.println("----------------------------------------------");
RecustionAllElementOfLinkedList.printAllElements(node1);
}
}
运行结果:
链表部分已完结，如果遇到新的，会持续更新……
参考资料：
程序员实用算法—Andrew Binstock / John Rex 机械工业出版 第二章第一节 链表 下载地址
时间复杂度分别为 O（n）和 O（1）的删除单链表结点的方法