单链表相交编程题——java实现

爱被打了一巴掌 2024-03-17 10:49 10阅读 0赞

题目：  
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。  
![在这里插入图片描述][07082feac9114b6c8f0df7f451bb93c9.png]

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

![在这里插入图片描述][602e684813234b04a3c94c245a024bec.png]

原题OJ链接https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

解答：

/**
     * 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 lenA = length(headA);
            int lenB = length(headB);
            int len = lenA -lenB;
    
            ListNode pl = new ListNode();
            ListNode ps = new ListNode();
    
            if(len >= 0){
        
                pl = headA;
                ps = headB;
            }
            else{
        
                len = lenB -lenA;
                ps = headA;
                pl = headB;
            }
            if(pl == null || ps == null){
        
                return null;
            }
            while(len>0){
        
                pl = pl.next;
                len--;
            }
            while(pl != ps){
        
                pl = pl.next;
                ps = ps.next;
            }
            return pl;
        }
        public static int length(ListNode head){
        
            ListNode cur = head;
            int length = 0;
            while(cur != null){
        
                cur = cur.next;
                length++;
            }
            return length;
        }
    }

[07082feac9114b6c8f0df7f451bb93c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/0c136ba0223e4bef97d4235eaa828974.png
[602e684813234b04a3c94c245a024bec.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/17/7d0320d1e5b64220ae180e2943cdc576.png