链表OJ题——相交链表

一、题目链接

相交链表
题目描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表的第一个公共结点。

二、解题思路

三、解题代码

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int len1 = 0;int len2 = 0;ListNode pl = headA;ListNode ps = headB;//1、求链表1的长度while(pl != null){len1++;pl = pl.next;}//1、求链表2的长度while(ps != null){len2++;ps = ps.next;}//由于遍历求链表长度后，两指针pl和ps已经都为null了//需要给他们重新赋值，不然后续再使用它们就会报空指针异常pl = headA;ps = headB;// 根据链表长度计算出两链表之间的差值int len = len1 - len2; //由于事先并不知道链表1和链表2到底谁更长，因此默认链表1为长链表，如果len < 0//就表示长链表为链表22，需要为他们重新赋值。if(len < 0){pl = headB;ps = headA;len = len2 - len1;}//长链表先走len步while(len != 0){pl = pl.next;len--;}//长链表走完差值步后，两链表开始一起走while(pl != ps){pl = pl.next;ps = ps.next;}//走到这里，有两种情况：1、pl == ps，表明在链表中是有相交的节点的。2、表明pl和ps都走到了链表的末尾，即pl和ps都等于null，表明两个链表遍历完了都没有相交的节点。if(pl == null || ps == null){return null; // 表明无相交的节点}return pl;}
}