两个链表的第一个公共节点（Java实现）
思路： 我们使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点；当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。
这样，当它们相遇时，所指向的结点就是第一个公共结点。
package Day40; /** * @Author Zhongger * @Description 找出两个链表相交的结点 * @Date 2020.3.12 */ public class FindCommentNode { public static void main(String[] args) { ListNode commentNode = new ListNode(5); ListNode headA = new ListNode(0); ListNode listNodeA1 = new ListNode(1); ListNode listNodeA2 = new ListNode(2); ListNode listNodeA3 = new ListNode(3); ListNode listNodeA4 = new ListNode(4); headA.next=listNodeA1; listNodeA1.next=listNodeA2; listNodeA2.next=listNodeA3; listNodeA3.next=listNodeA4; listNodeA4.next=commentNode; ListNode headB = new ListNode(0); ListNode listNodeB1 = new ListNode(1); ListNode listNodeB2 = new ListNode(3); headB.next=listNodeB1; listNodeB1.next=listNodeB2; listNodeB2.next=commentNode; FindCommentNode findCommentNode = new FindCommentNode(); System.out.println(findCommentNode.getIntersectionNode(headA, headB)); } public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int length1 = getLength(headA); int length2 = getLength(headB); ListNode ptr1 = headA, ptr2 = headB; if (length1 < length2) { ptr1 = headB; ptr2 = headA; } int count = Math.abs(length1 - length2); while (ptr1 != null && count > 0) { ptr1 = ptr1.next; count--; } while (ptr1 != null && ptr2 != null) { if (ptr1 == ptr2) { return ptr1; } ptr1 = ptr1.next; ptr2 = ptr2.next; } return null; } private int getLength(ListNode head) { int count = 0; while (head != null) { count++; head = head.next; } return count; } } class ListNode{ int val; ListNode next; public ListNode(int val){ this.val=val; } @Override public String toString() { return "ListNode{" + "val=" + val + '}'; } }
