【Hot100】LeetCode—160. 相交链表

---

• 原题连接：160. 相交链表

---

1- 思路

思路

• 首先想要找到相交点，需要定义连个指针。两个指针一定得是同步的，例如 A 链表 [1,2,3,4,5] ，链表 B 是 [4,5]
  • 1- 指针对齐：则需要指针1 先移动，移动长度为 lenA - lenB
  • 2- 同时移动：移动指针1 和 指针2 ，遇到相等则返回相等结点，否则返回 null

---

2- 实现

⭐160. 相交链表——题解思路

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode nodeA = headA;ListNode nodeB = headB;int lenA = 0;int lenB = 0;while(nodeA!=null){lenA++;nodeA = nodeA.next;}while(nodeB!=null){lenB++;nodeB = nodeB.next;}if(lenB>lenA) return getIntersectionNode(headB,headA);nodeA = headA;nodeB = headB;// 1. 先移动第一个指针 for(int i = 0 ; i < lenA-lenB;i++){headA = headA.next;}while(headA!=null || headB!=null){if(headA==headB){return headA;}headA = headA.next;headB = headB.next;}return null;}
}

---

3- ACM 实现

public class getIntersectionNode {public static class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}public static ListNode getIntersection(ListNode head1,ListNode head2){ListNode curA = head1;ListNode curB = head2;int len1 = 0;int len2 = 0;while(curA!=null){len1++;curA = curA.next;}while(curB!=null){len2++;curB = curB.next;}if(len1<len2) return getIntersection(head2,head1);// 遍历curA = head1;curB = head2;while (curA!=null || curB !=null){if(curA == curB){return curA;}curA = curA.next;curB = curB.next;}return null;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取第一个链表的节点数量int n1 = sc.nextInt();ListNode head1 = null, tail1 = null;for (int i = 0; i < n1; i++) {int val = sc.nextInt();ListNode newNode = new ListNode(val);if (head1 == null) {head1 = newNode;tail1 = newNode;} else {tail1.next = newNode;tail1 = newNode;}}// 读取第二个链表的节点数量int n2 = sc.nextInt();ListNode head2 = null, tail2 = null;for (int i = 0; i < n2; i++) {int val = sc.nextInt();ListNode newNode = new ListNode(val);if (head2 == null) {head2 = newNode;tail2 = newNode;} else {tail2.next = newNode;tail2 = newNode;}}// 读取交点位置int intersectionIndex = sc.nextInt();if (intersectionIndex >= 0) {ListNode intersectionNode = head1;for (int i = 0; i < intersectionIndex; i++) {if (intersectionNode != null) {intersectionNode = intersectionNode.next;}}if (tail2 != null) {tail2.next = intersectionNode;}}System.out.println("结果是"+getIntersection(head1,head2).val);}
}