赞
踩
问题描述:
有两个单向链表他们可能相交,也可能不相交。若相交则返回相交的节点,若不相交则返回null。
两个单向链表相交,有且仅有三种情况。
链表相交的问题算是链表问题中最难的问题之一了!!!!
实现流程:
代码实现如下:
public static SingleNode findFistIntersectNode01(SingleNode head1, SingleNode head2) { if (head1 == null || head2 == null) { return null; } final HashSet<SingleNode> set = new HashSet<>(); // 先选一条链表,将这条链表的所有节点加入到hash表中 while (head1 != null) { set.add(head1); head1 = head1.next; } // 遍历第二条链表,每遍历一个节点都去set集合中检查一下该节点是否加入过,如果加入过则该节点就是两个链表的相交节点 while (head2 != null) { if (set.contains(head2)) { return head2; } head2 = head2.next; } // 如果第二条链表都遍历完了都没有在set集合中找到相同的节点,则两条链表不相交 return null; }
node定义
@Data public class SingleNode<T> { public T value; public SingleNode next; public SingleNode() {} public SingleNode(final T data) { this.value = data; } @Override public boolean equals(final Object o) { if (this == o) return true; if (o == null || this.getClass() != o.getClass()) return false; final SingleNode that = (SingleNode) o; return Objects.equals(this.value, that.value); } @Override public int hashCode() { return Objects.hash(this.value); } @Override public String toString() { return (String) this.value; } }
实现流程:
- 通过先遍历两个链表的长度,然后取各自链表的最后一个节点,比较这两个节点是否相等。若相等则相交,反之则不相交。
- 如果相交,则将长链表的长度 减去 短链表的长度,然后长链表先走差值步。
- 然后短链表再从链表头开始走,长链表也继续走,直到他们走到的节点内存地址一样,该节点就是他们相交的节点。
/** * @param head1 第一个链表的头节点 * @param head2 第二个链表的头节点 * @description: 通过遍历两个链表的方式来实现查找两个单向链表相交节点 * @return: com.wp.algorithm.common.SingleNode 返回相交的节点 * @date: 2021/3/25 1:28 下午 * @auther: Mr_wenpan@163.com */ public static SingleNode findFistIntersectNode02(final SingleNode head1, final SingleNode head2) { if (head1 == null || head2 == null) { return null; } SingleNode current1 = head1; SingleNode current2 = head2; int listOneLength = 0; int listTwoLength = 0; // 统计链表1的长度,并且 current1 停在最后一个节点 while (current1.next != null) { listOneLength++; current1 = current1.next; } // 统计链表2的长度,并且 current2 停在最后一个节点 while (current2.next != null) { listTwoLength++; current2 = current2.next; } // 若相交,则两条链表最后一个节点一定是一样的。若不一样,则不相交。 if (current1 != current2) { return null; } // 求两条链表的长度差值 int d = listOneLength - listTwoLength; // 定义长、短链表指针,分别指向长链表和短链表头 SingleNode longList; SingleNode shortList; // 如果d > 0则说明第一条链表是长链表,反之第二条链表是长链表 if (d > 0) { longList = head1; shortList = head2; } else { longList = head2; shortList = head1; } d = Math.abs(d); // 长链表先走差值步 for (int i = 0; i < d; i++) { longList = longList.next; } // 长短链表一起走,直到相遇时退出循环 while (longList != shortList) { longList = longList.next; shortList = shortList.next; } // 返回相遇的节点 return longList; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
第一种情况下两个单链表没有环状结构,相遇节点就是相交节点。
在这种情况中,由于两个链表有环,所以就不能统计出每条链表的具体长度了,但仍然可以使用计算链表长度的方法来做。
解决方案有两种:
第一种是使用hash表的方式
第二种是先找到这个两个链表的环的入口节点,然后计算两个链表从头节点到入环节点的长度差值,让长链表先走差值步,然后两个链表指针再一起走,直到相遇,相遇的节点就是他们相交的节点。
代码如下:
/** * @param head1 第一个链表的头节点 * @param head2 第二个链表的头节点 * @description: 通过hash表 + 遍历两个链表的方式来实现查找两个单向链表相交节点(相交的两条链表有无环结构都适用) * @return: com.wp.algorithm.common.SingleNode 返回相交的节点 * @auther: Mr_wenpan@163.com */ public static SingleNode findFistIntersectNode03(final SingleNode head1, final SingleNode head2) { if (head1 == null || head1 == null) { return null; } final HashSet<SingleNode> hashSet = new HashSet<>(); SingleNode current1 = head1; SingleNode current2 = head2; while (current1 != null && current2 != null) { // 先判断是否存在hash表中,不存在则添加,若存在,则该节点就是两条链表相交的节点 if (hashSet.contains(current1)) { return current1; } hashSet.add(current1); if (hashSet.contains(current2)) { return current2; } hashSet.add(current2); current1 = current1.next; current2 = current2.next; } return null; }
代码实现如下:
/** * 情况二、相交有环、且入环的节点和相交节点不同,但入环节点一样 * 通过遍历两条链表来做 */ public static SingleNode findFistIntersectNode04(final SingleNode head1, final SingleNode head2) { SingleNode cur1 = head1; SingleNode cur2 = head2; // 两条链表从头节点开始,到两条链表入环节点的长度 int length1 = 0; int length2 = 0; // 1、先找到入环节点 final SingleNode cycleNode1 = findInCycleNode(cur1); final SingleNode cycleNode2 = findInCycleNode(cur2); // 两个链表不相交的情况 if (cycleNode1 != cycleNode2 || cycleNode1 == null || cycleNode2 == null) { return null; } // 2、计算两条链表从头节点到入环节点的长度 while (cur1 != cycleNode1) { cur1 = cur1.next; length1++; } while (cur2 != cycleNode1) { cur2 = cur2.next; length2++; } // 3、找出长链表 并 计算两条链表从头节点到入环节点的长度差值 SingleNode longList = length1 > length2 ? head1 : head2; SingleNode shortList = longList == head1 ? head2 : head1; final int diff = Math.abs(length1 - length2); // 4、长链表先走差值步 for (int i = 0; i < diff; i++) { longList = longList.next; } // 5、长短链表一起走,直到相遇,返回相遇节点即是两条链表的相交节点 while (longList != shortList) { longList = longList.next; shortList = shortList.next; } // 返回两条链表相交节点 return longList; } /** * 查找一条链表的入环节点 */ public static SingleNode findInCycleNode(final SingleNode head) { if (head == null) { return null; } SingleNode fast = head; SingleNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; // 慢指针追上快指针 if (fast == slow) { break; } } // 两个链表不相交的情况 if (fast == null || fast.next == null) { return null; } // 快指针从头开始走 fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } // 返回相交节点 return fast; }
这种相交的情况比较特殊:他有两个相交点,并且入环节点都不一样。这两个入环节点都是链表的相交节点,只用返回任意一个即可。
查找步骤如下:
- 分别查找出两条链表的入环节点,两个指针分别停留在两个入环节点。
- 第一个指针停留在第一个链表的入环节点不动
- 第二个指针从第二个链表的入环节点开始一步一步的往下走一圈。
- 如果第二个指针在遍历他的环的过程中能遇上第一个入环节点,则返回该节点即可(该节点就是两条链表相交的节点)
- 如果第二个指针已经遍历了环一周,任然没有遇到第一个链表的入环节点。则直接返回空即可(说明两条链表不相交)。
代码如下:
public static SingleNode findFistIntersectNode05(final SingleNode head1, final SingleNode head2) { // 1、先找到两个链表的入环节点 final SingleNode cycleNode1 = findInCycleNode(head1); final SingleNode cycleNode2 = findInCycleNode(head2); // 定义两个指针分别指向两个节点 SingleNode cur1; final SingleNode cur2 = cycleNode2; // 入环节点不一样 if (cycleNode1 != cycleNode2) { // 第一个指针停在第一个入环节点不动,第二个指针从第二个入环节点开始绕环一周,看看能不能遇到第一个入环节点 cur1 = cycleNode2.next; while (cur1 != cycleNode2) { // 如果cur2在遍历环的时候遇到了cur1,则直接返回cur1,cur1或cur2就是他们相交的节点 if (cur1 == cur2) { return cur1; } cur1 = cur1.next; } } return null; }
上面对链表相交的三种情况逐一做了分析与代码实现,此时我们就应该将三种情况进行整合。这里先整合情况二和情况三,这两种情况是相交且有环的情况。
这里比上面的分情况讨论的代码做了精简!!!!
代码示例
/** * @param head1 第一个单向链表的头节点 * @param loop1 第一个入环节点,需要自己查找然后传入 * @param head2 第二个单向链表的头节点 * @param loop2 第二个入环节点,需要自己查找然后传入 * @description: 查找两个单向链表相遇节点的代码演示,该方法能处理两个链表相交并且有环的情况 * @return: com.wp.algorithm.common.SingleNode 返回相遇的节点 * @auther: Mr_wenpan@163.com */ public static SingleNode bothLoop(final SingleNode head1, final SingleNode loop1, final SingleNode head2, final SingleNode loop2) { SingleNode cur1; SingleNode cur2; // 一、两个链表的入环节点是同一个 if (loop1 == loop2) { cur1 = head1; cur2 = head2; int n = 0; // 求出两个链表的长度差值n(从链表头节点到入环节点的长度差值 n) while (cur1 != loop1) { n++; cur1 = cur1.next; } while (cur2 != loop2) { n--; cur2 = cur2.next; } // 如果 n>0 则说明head1这条链表比head2这条链表长 // 这里的作用就是让cur1指向长的那条链表,让cur2指向短的那条链表 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 { // 二、如果两个链表的入环节点不是同一个 cur1 = loop1.next; // cur1从第一个入环节点走一圈 while (cur1 != loop1) { // 如果能遇上第二个入环节点就返回,如果一直遇不上,则说明不存在,直接返回空 if (cur1 == loop2) { return loop1; } cur1 = cur1.next; } // 如果找不到,则返回空 return null; } }
将三种情况做一个统一的整合,整合为一个方法。
代码示例
public static SingleNode findCommonNode(final SingleNode head1, final SingleNode head2) { // 1、先找到两个链表的入环节点 final SingleNode cycleNode1 = findInCycleNode(head1); final SingleNode cycleNode2 = findInCycleNode(head2); final boolean flag = (cycleNode1 == null && cycleNode2 != null) || (cycleNode2 == null && cycleNode1 != null); // 两个链表不相交,一个有环一个无环的情况 if (flag) { return null; } // 一、没有环的情况 if (cycleNode1 == null) { return findFistIntersectNode02(head1, head2); } else { // 二、有环的情况 return bothLoop(head1, cycleNode1, head2, cycleNode2); } }
public static void main(final String[] args) { // 创建第一条链表 final SingleNode<String> node1 = new SingleNode<>("1"); final SingleNode<String> node2 = new SingleNode<>("2"); final SingleNode<String> node3 = new SingleNode<>("3"); final SingleNode<String> node4 = new SingleNode<>("4"); final SingleNode<String> node5 = new SingleNode<>("5"); final SingleNode<String> node6 = new SingleNode<>("6"); node1.next = node2; node2.next = node3; node3.next = node4; node4.next = node5; node5.next = node6; node6.next = node3; // 创建第二条链表 final SingleNode<String> node11 = new SingleNode<>("11"); final SingleNode<String> node12 = new SingleNode<>("12"); final SingleNode<String> node13 = new SingleNode<>("13"); final SingleNode<String> node14 = new SingleNode<>("14"); final SingleNode<String> node15 = new SingleNode<>("15"); final SingleNode<String> node16 = new SingleNode<>("16"); node11.next = node12; node12.next = node13; node13.next = node14; node14.next = node15; node15.next = node3; final SingleNode commonNode = findCommonNode(node1, node11); System.out.println(commonNode); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。