算法(13)-链表相交

链表

 2024/03/11 

题目(easy)：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

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

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

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

思路

先移动长度差值的长度。

const getListLen = (head) => {
    let len = 0, cur = head;
    while(cur) {
       len++;
       cur = cur.next;
    }
    return len;
}

const getIntersectionNode = (headA, headB) => {
    let curA = headA;
    let curB = headB;
    let lenA = getListLen(headA);
    let lenB = getListLen(headB);
    if (lenA < lenB) {
        [curA, curB] = [curB, curA];
        [lenA, lenB] = [lenB, lenA];
    }
    let i = lenA - lenB;
    while(i-- > 0) {
        curA = curA.next;
    }
    while(curA && curA !== curB) {
        curA = curA.next;
        curB = curB.next;
    }
    return curA;
}

原文作者：Yizhou Shen

原文链接：http://shenyizhou.github.io/2024/03/11/2024-03-11-%E7%AE%97%E6%B3%95(13)-%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4/

发表日期：March 11th 2024, 9:29:59 am

更新日期：March 17th 2024, 9:39:07 am

Next Post

算法(14)-环形链表II
Previous Post

算法(12)-删除链表的倒数第N个节点

CATALOG

1. 题目(easy)：
2. 思路