Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

160. 相交链表 #36

Closed
sailei1 opened this issue May 22, 2019 · 0 comments
Closed

160. 相交链表 #36

sailei1 opened this issue May 22, 2019 · 0 comments

Comments

@sailei1
Copy link
Owner

sailei1 commented May 22, 2019

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

如下面的两个链表:

image

在节点 c1 开始相交。

示例 1:

image

输入: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:

image

输入: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:

image

输入: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) 内存。

思路:
根据长度不一样,找到公共长度的尾部
A尾部 跟B 尾部 对比 根据结果返回

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

var getIntersectionNode = function(headA, headB) {   
  let lena = getLen(headA);  
  let lenb = getLen(headB); 
  
  let a = headA;
  let b = headB;
  if (lena > lenb) {
    let tem = lena - lenb
    for (let i=0; i<tem; i++) {
      a = a.next;
    }
  } else {
    let tem = lenb - lena
    for (let i=0; i<tem; i++) {
      b = b.next;
    }
  }
    //找到一样长度的尾部
 
    
  while (a) {
    if (a === b) {
      return a;
    }
    a = a.next;
    b = b.next;
  }
  return null;
};

function getLen(list) { //获取长度
  let len = 0;
  while (list) {
    len += 1;
    list = list.next;
  }
  return len;
}

@sailei1 sailei1 closed this as completed May 22, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant