Skip to content

图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点 #17

Open
Open
图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点#17
Labels
LeetCode字节

Description

@sisterAn
sisterAn
opened on Apr 14, 2020

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

 

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

  • 如果两个链表没有交点，返回 null.
  • 在返回结果后，两个链表仍须保持原有的结构。
  • 可假定整个链表结构中没有循环。
  • 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

附leetcode地址：leetcode

Activity

  1. sisterAn
    changed the title [-]字节leetcode160：相交链表[/-] [+]字节&leetcode160：相交链表[/+] on Apr 14, 2020
  2. sisterAn
    changed the title [-]字节&leetcode160：相交链表[/-] [+]字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点[/+] on Apr 14, 2020

  3. hh-cheng commented on Apr 14, 2020

    @hh-cheng
    hh-cheng
    on Apr 14, 2020

    方法：遍历

    • 先将两个链表转换成数组结构
    • 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
    • 遍历结束后如果没有找到就返回 null
    function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;

    /*
        arr1.some( value => {
            if ( arr2.includes(value) ){
                theValue = value;
                return true;
            }
        })
        if( theValue ){
            return 'Reference of the node with value = ' + theValue;
        } 
        return null;
    */
}

function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

    测试代码：

    function CreateNode(val){
    this.val = val;
    this.next = null;
}
function CreateList(...nodes){
    this.head = nodes[0];
    this.length = nodes.length;
    for( var i = 0; i < nodes.length - 1; i++ ){
        if( nodes[i+1] ){
            nodes[i].next = nodes[i+1];
        }
    }
}

function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;
}
function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

  4. hecun0000 commented on Apr 15, 2020

    @hecun0000
    hecun0000
    on Apr 15, 2020
    1. 将一个链表的值放入 map, 遍历另一个链表，判断有无该节点
    var getIntersectionNode = function (headA, headB) {
  var map = new WeakMap()
  while (headA) {
    map.set(headA, true)
    headA = headA.next
  }
  while (headB) {
    var curr = map.get(headB)
    if (curr) return headB
    headB = headB.next
  }
  return null
};

  5. sisterAn commented on Apr 15, 2020

    @sisterAn
    sisterAn
    on Apr 15, 2020
    OwnerAuthor

    解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

    解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

    若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

    const getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(n)

    解法二：双指针法

    解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

    我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

    解题步骤：

    • 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
    • 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
    • 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
    • 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

    画图帮助理解：

    const getIntersectionNode = function(headA, headB) {
    // 清除高度差
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(1)

    leetcode

  6. sisterAn commented on Apr 15, 2020

    @sisterAn
    sisterAn
    on Apr 15, 2020
    OwnerAuthor

    方法：遍历

    • 先将两个链表转换成数组结构
    • 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
    • 遍历结束后如果没有找到就返回 null
    function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;

    /*
        arr1.some( value => {
            if ( arr2.includes(value) ){
                theValue = value;
                return true;
            }
        })
        if( theValue ){
            return 'Reference of the node with value = ' + theValue;
        } 
        return null;
    */
}

function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

    测试代码：

    function CreateNode(val){
    this.val = val;
    this.next = null;
}
function CreateList(...nodes){
    this.head = nodes[0];
    this.length = nodes.length;
    for( var i = 0; i < nodes.length - 1; i++ ){
        if( nodes[i+1] ){
            nodes[i].next = nodes[i+1];
        }
    }
}

function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;
}
function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

    想法不错，不过可以进阶一下，使用双指针来做，使之尽量满足空间复杂度O(1)

  7. sisterAn
    changed the title [-]字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点[/-] [+]图解字节&leetcode160：编写一个程序，找到两个单链表相交的起始节点[/+] on Apr 15, 2020
  8. sisterAn
    added
    LeetCode
    字节
    on May 5, 2020

  9. cs739295 commented on Jun 15, 2020

    @cs739295
    cs739295
    on Jun 15, 2020

    方法：遍历

    • 先将两个链表转换成数组结构
    • 对其中一个数组进行遍历，每次遍历判断另一个数组是否含有该值
    • 遍历结束后如果没有找到就返回 null
    function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;

    /*
        arr1.some( value => {
            if ( arr2.includes(value) ){
                theValue = value;
                return true;
            }
        })
        if( theValue ){
            return 'Reference of the node with value = ' + theValue;
        } 
        return null;
    */
}

function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

    测试代码：

    function CreateNode(val){
    this.val = val;
    this.next = null;
}
function CreateList(...nodes){
    this.head = nodes[0];
    this.length = nodes.length;
    for( var i = 0; i < nodes.length - 1; i++ ){
        if( nodes[i+1] ){
            nodes[i].next = nodes[i+1];
        }
    }
}

function intersectNode( head1, head2 ) {
    var arr1 = [],
        arr2 = [],
        theValue = null;
    transformToArray( head1, arr1 );
    transformToArray( head2, arr2 );

    for (var i = 0; i < arr1.length; i++) {
        if( arr2.indexOf(arr1[i]) !== -1 ){
            theValue = arr1[i];
            return 'Reference of the node with value = ' + theValue;
        }
    }
    return theValue;
}
function transformToArray( head, arr ) {
    while( head ){
        arr.push(head.val);
        head = head.next;
    }
}

const node1 = new CreateNode(1);
const node2 = new CreateNode(2);
const node3 = new CreateNode(3);
const node4 = new CreateNode(4);
const node5 = new CreateNode(5);
const nodeA = new CreateNode('A');
const nodeB = new CreateNode('B');
const nodeC = new CreateNode('C');
const nodeD = new CreateNode('D');
const nodeE = new CreateNode('E');
const list1 = new CreateList(node1, node2, node3, node4, node5);
const list2 = new CreateList(nodeA, nodeB, node3, nodeC, nodeD);

intersectNode(list1.head, list2.head);

    想法不错，不过可以进阶一下，使用双指针来做，使之尽量满足空间复杂度O(1)

    解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

    解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

    若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

    var getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(n)

    解法二：双指针法

    解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

    我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

    解题步骤：

    • 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
    • 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
    • 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
    • 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

    画图帮助理解：

    var getIntersectionNode = function(headA, headB) {
    // 清除高度差
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(1)

    leetcode

    你好，我想问一下，if(pA === pB) return pA。这行代码怎么理解？题目表示是两个单独的链表，链表里的节点都是对象，对象的这种===会有效吗？他们两个好像是指向不同的地址空间把。是不是应该比较pA与pB的值才行。改为if(pA.val===pB) return pA;会不会更好一点？

  10. Been101 commented on Jul 18, 2020

    @Been101
    Been101
    on Jul 18, 2020
    const getIntersectionNode = (head1, head2) => {
        const h1 = head1
        const h2 = head2
        while (h1 || h2) {
          if(h1.data === h2.data) return h1
          h1 = h1 === null ? head2 : h1.next
          h2 = h2 === null ? head1 : h2.next
        }
        return null
      }

  11. AnranS commented on Nov 17, 2020

    @AnranS
    AnranS
    on Nov 17, 2020

    WeakMap

    var getIntersectionNode = function (headA, headB) {
    let currenA = headA, currenB = headB;
    let map = new WeakMap();
    while(currenA) {
        map.set(currenA, true);
        currenA = currenA.next;
    }

    while(currenB) {
        if(map.has(currenB)) return currenB.val;
        currenB = currenB.next;
    }
    return null;
};

    双指针

    var getIntersectionNode = function (headA, headB) {
    let currentA = headA, currentB = headB;
    while(currentA || currentB) {
        if(currentB === currentA) return currentA;
        currentA = currentA === null ? headB : currentA.next; 
        currentB = currentB === null ? headA : currentB.next; 
    }
    return null;
};

  12. xiaoerwen commented on Apr 8, 2021

    @xiaoerwen
    xiaoerwen
    on Apr 8, 2021
    const getIntersectionNode = (headA, headB) => {
    if (!headA || !headB) {
        return null;
    }

    let tailA = headA;
    let tailB = headB;
    let stackA = [];
    let stackB = [];
    // 获取链表A的尾结点
    while (tailA.next) {
        stackA.push(tailA);
        tailA = tailA.next;
    }
    // 获取链表B的尾结点
    while (tailB.next) {
        stackB.push(tailB);
        tailB = tailB.next;
    }

    let count = 1;
    while (stackA.length && stackB.length) {
        // 如果尾结点相等，往前移动指针
        if (tailA === tailB) {
            tailA = stackA.pop();
            tailB = stackB.pop();
            count++;
        }
        // 否则代表到了不相交初了，终止遍历
        else {
            break;
        }
    }

    /**
     * count为1有两种情况
     * 第一种：链表A和链表B都只有一个节点，那么判断他们是否相等即可
     * 第二种：遍历俩链表都没有相等的节点，证明俩链表不相交，返回null
     */
    if (count === 1) {
        return tailA === tailB ? tailA : null;
    }

    /**
     * 同理存在两种情况
     * 第一种：遍历完俩链表，每个节点都相等，那么返回头节点
     * 第二种：在不相交的节点处循环中断了，相交节点应该等于当前节点的下一个节点
     */
    return tailA === tailB ? tailA : tailA.next;
};

  13. JohnApache commented on Apr 27, 2021

    @JohnApache
    JohnApache
    on Apr 27, 2021

    解法一：标记法(简单但空间复杂度为O(n)，不符合，仅做参考)

    解题思路： 两次遍历，先遍历一个链表，给链表中的每个节点都增加一个标志位，然后遍历另外一个链表，遍历到第一个已被标志过的节点为两链表相交的起始节点。

    若遍历完都没有发现已被标志过的节点，则两链表不相交，返回 null

    const getIntersectionNode = function(headA, headB) {
    while(headA) {
        headA.flag = true
        headA = headA.next
    }
    while(headB) {
        if (headB.flag) return headB
        headB = headB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(n)

    解法二：双指针法

    解题思路： 如果 A、B 两链表相交，则 A 、B 自相交点往后的链表是一致的。

    我们可以尝试消除 A、B 链表的长度差，同步遍历上图中的方框里的节点，判断是否有相同节点，若有相同则是两链表相交，返回第一个相同节点 即可。否则返回 null ，两链表不相交。

    解题步骤：

    • 同步遍历 A、B 链表 pA 、 pB ，直到遍历完其中一个链表（短链表），如上图，设A为长链表
    • 那么此时 A、B 两遍表的长度差就为 pA 到链尾的长度，此时可以把 pB 指向长链表的表头 headA ，继续同步遍历，直到遍历完长链表
    • 此时，headA 到 pB 的长度就为两链表的长度差，pB 到链表的长度与 headB 到链尾的长度一致
    • 此时，可将 pA 指向 headB ，然后同步遍历 pB 及 pA ，直到有相交节点，返回相交节点，否则返回 null

    画图帮助理解：

    const getIntersectionNode = function(headA, headB) {
    // 清除高度差
    let pA = headA, pB = headB
    while(pA || pB) {
        if(pA === pB) return pA
        pA = pA === null ? headB : pA.next
        pB = pB === null ? headA : pB.next
    }
    return null
};

    时间复杂度：O(n)

    空间复杂度：O(1)

    leetcode

    我觉得 双指针消除高度差的方案， 时间复杂度并不是 On , 在 极限差的情况下 [4,1,8,4,5] , [5,0,1,8,4,5]，假如相交的节点是最后一个点，会出现 遍历两遍链表的情况, 。

    我自己实现了的方案，也是 双指针，但是最多只会遍历一次，不会出现遍历两遍的情况，

    class Node {
    public next: Node | undefined;
    constructor (public element: any) {}
}
const getInsersectionNode = (headA: Node, headB: Node) => {
    const map = new Map();
    if (headA === headB) return headA;
    let nextA: Node | undefined = headA;
    let nextB: Node | undefined = headB;
    while (nextA || nextB) {
        if (map.get(nextA)) return nextA;
        if (map.get(nextB)) return nextB;
        if (nextA) {
            map.set(nextA, true);
            nextA = nextA.next;
        }
        if (nextB) {
            map.set(nextB, true);
            nextB = nextB.next;
        }
    }
    return undefined;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    LeetCode字节

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions