java-双链表

public class TestDemo {
    //18.输入两个链表，找出他们的第一个公共节点（相交的起始节点）
    
    public static Node getIntersectionNode(Node headA,Node headB) {
        //18.求两个单链表的长度,计算两个长度差
        int lenA = 0;
        int lenB = 0;
        Node pl = headA;
        Node ps = headB;
        while(pl != null){
            pl = pl.next;
            lenA++;
        }
        while(ps != null){
            ps = ps.next;
            lenB++;
        }
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //此时pl一定指向最长
        for (int i = 0;i < len;i++) {
            pl = pl.next;
        }
        //此时pl和ps在同一起跑线
        while(ps != pl &&pl != null && ps != null){
            ps = ps.next;
            pl = pl.next;
        }
        if (ps == pl &&pl != null){
            return pl;
        }
        return null;
    }


    //19.将两个升序链表合并为一个新的升序链表并返回
    public static Node mergeTwoLists(Node headA,Node headB) {
        Node newHead = new Node(-1);
        Node tmp = newHead;
        if(headA == null){
            return headB;
        }
        if(headB == null){
            return headA;
        }
        while(headA != null && headB != null) {
            if (headA.data < headB.data){
                tmp.next = headA;
                tmp = tmp.next;
                headA = headA.next;
            }
            else{
                tmp.next = headB;
                tmp = tmp.next;
                headB = headB.next;
            }
            if (headA != null){
                tmp.next = headA;
            }
            if (headB != null){
                tmp.next = headB;
            }
        }
        return newHead.next;
    }