企业网站有什么用,网站建设 重点,东莞有哪家比较好的网站建设公司,上海好的设计公司问题描述 RT. 解决思路 (1) 两链表都是单向链表#xff1a;判断两链表的末尾节点是否相同#xff1b; (2) 两链表中一个有环#xff0c;一个没环#xff1a;不可能相交#xff1b; (3) 两链表都有环#xff1a;slow-fast双指针方法。 程序 public class ListIntersection…问题描述 RT. 解决思路 (1) 两链表都是单向链表判断两链表的末尾节点是否相同 (2) 两链表中一个有环一个没环不可能相交 (3) 两链表都有环slow-fast双指针方法。 程序 public class ListIntersection {// two single listpublic boolean isIntersectionOfTwoSingleList(ListNode l1, ListNode l2) {if (l1 null || l2 null) {return false;}// whether the end of two list is sameListNode endOfList1 getEndOfList(l1);ListNode endOfList2 getEndOfList(l2);return endOfList1 endOfList2;}private ListNode getEndOfList(ListNode head) {if (head null) {return null;}ListNode node head;while (node.next ! null) {node node.next;}return node;}// two list with cyclepublic boolean isIntersectionOfTwoListWithCycle(ListNode l1, ListNode l2) {if (l1 null || l2 null) {return false;}ListNode slow l1, fast l2;while (fast.next ! null || fast ! null || slow ! null) {slow slow.next;fast fast.next.next;if (slow fast) {return true;}}return false;}
}Follow up 求出两个链表相交的第一个节点如果存在的话。 (1) 两条单链表 a. 求出两条链表的长度及长度之差diff然后设立两个指针指向两链表的头结点其中指向长链表头结点的指针向前移动diff步 b. 然后同时移动两指针直到所指节点相同地址相同为止否则返回null。 (2) 两条链表有环 首先slow-fast直到相遇为止其中任意一个指针指回其头结点然后slow和fast指针同时移动直到相遇相遇的节点为第一个相交的节点。 注意可能有两个相交的节点 程序 public class ListIntersection2 {// two single listpublic ListNode getFirstIntersectionNodeOfSingleList(ListNode l1,ListNode l2) {ListNode longNode l1, shortNode l2;int len1 getLenOfList(l1);int len2 getLenOfList(l2);if (len1 len2) {longNode l2;shortNode l1;}int diff Math.abs(len1 - len2);// long move diff stepswhile (diff 0) {longNode longNode.next;--diff;}while (longNode ! null shortNode ! null) {if (longNode shortNode) {return longNode;}longNode longNode.next;shortNode shortNode.next;}return null;}private int getLenOfList(ListNode head) {ListNode node head;int len 0;while (node ! null) {len;node node.next;}return len;}// two list with cyclepublic ListNode getFirstIntersectionNodeOfCycleList(ListNode l1, ListNode l2) {if (l1 null || l2 null) {return null;}ListNode slow l1, fast l2;while (fast.next ! null || fast ! null || slow ! null) {if (fast slow) {break;}slow slow.next;fast fast.next.next;}if (fast null || slow null) {return null;}slow l1;while (slow ! fast) {slow slow.next;fast fast.next;}return slow;}
}转载于:https://www.cnblogs.com/harrygogo/p/4614277.html
