题目
题目来源leetcode
leetcode地址：面试题 02.07. 链表相交，难度：简单。
题目描述(摘自leetcode)：
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 图示两个链表在节点 c1 开始相交： 题目数据 保证 整个链式结构中不存在环。 注意，函数返回结果后，链表必须 保持其原始结构 。 示例 1： 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。 在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。 示例 2： 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 输出：Intersected at '2' 解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。 从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。 在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。 示例 3： 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 输出：null 解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。 由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。 这两个链表不相交，因此返回 null 。 提示： listA 中节点数目为 m listB 中节点数目为 n 0 <= m, n <= 3 * 104 1 <= Node.val <= 105 0 <= skipA <= m 0 <= skipB <= n 如果 listA 和 listB 没有交点，intersectVal 为 0 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]
本地调试代码：
class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ... } public static void main(String[] args) { //公共节点 ListNode node2 = new ListNode(4, null); ListNode node1 = new ListNode(3, node2); //链表A ListNode aNode2 = new ListNode(2, node1); ListNode aNode1 = new ListNode(1, aNode2); //链表B ListNode bNode1 = new ListNode(1, node1); //测试 ListNode intersectionNode = new Solution().getIntersectionNode(aNode1, bNode1); //遍历 printList(intersectionNode); } private static void printList(ListNode listNode) { if(listNode == null){ return; } System.out.print("["); while(listNode != null){ System.out.print(listNode.val); if(listNode.next != null){ System.out.print(","); } listNode = listNode.next; } System.out.print("]"); } }
题解
NO1：差值移动比较法
思路：题目说要找到对应两个链表中公共的链表头节点，首先我们求出两个链表的长度，让长的链表先移动指定的差值，此时两个链表长度一致，接着两个链表同时向后移动节点进行比对即可找出头节点。
代码：时间复杂度O(n+m)
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int intersectVal = 0; //求A、B链表各自的长度 int aSize = getListSize(headA); int bSize = getListSize(headB); if(aSize == 0 || bSize == 0){ return null; } //长度差值 int moveStep = Math.abs(aSize-bSize); ListNode maxList = null; ListNode minList = null; if(aSize>bSize){ maxList = headA; minList = headB; }else if(aSize<bSize){ maxList = headB; minList = headA; }else{ maxList = headA; minList = headB; } //让长的进行移动差值步 for (int i = 1; i <= moveStep; i++) { maxList = maxList.next; } //此时大家从同一最后步长开始移动 while(maxList != null ){//这里任意取某一个为不为空情况 if(maxList == minList){ //比较的是对象是否相当，是否为同一个节点 return maxList; } maxList = maxList.next; minList = minList.next; } //链表不相交情况 return null; } public int getListSize(ListNode head){ int num = 0; while(head != null){ num++; head = head.next; } return num; }
