LeetCode-160.相交链表

发表于 分类于

题目描述

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

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

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

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

示例1

1
2
3
输入：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

1
2
3
4
输入：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。

题解

方法1

  • 单独的遍历两个链表，得到各自的长度。
  • 求得两链表的长度差，其中较长的链表的指针从头先走n步。
  • 两链表指针同步向后遍历，遇到第一个相同的节点就是第一个公共结点。

swift实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 单向链表节点
class ListNode {
  var val: Int
  var next: ListNode?
  init(_ val: Int) {
      self.val = val
      self.next = nil
  }
}
/** 获取两个链表相交节点 */
func getIntersectionNode(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
  let length1 = nodeLength(headA)
  let length2 = nodeLength(headB)
  var n = length1 - length2
  var fast: ListNode? = nil
  var slow: ListNode? = nil
  if (n > 0) {
    fast = headA
    slow = headB
  } else {
    n = length2 - length1
    fast = headB
    slow = headA
  }
  while(n > 0) {
    fast = fast?.next
    n -= 1
  }
  while (fast !== slow) {
    fast = fast?.next
    slow = slow?.next
  }
  return slow
}
/**获取链表长度 */
func nodeLength(_ head: ListNode?) -> Int {
  var cur = head
  var n = 0
  while (cur !== nil) {
    n += 1
    cur = cur?.next
  }
  return n
}

Javascript 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function ListNode(val) {
  this.val = val;
  this.next = null;
}

var getIntersectionNode = function (headA, headB) {
  const length1 = nodeLength(headA)
  const length2 = nodeLength(headB)
  let n = length1 - length2
  let fast = null
  let slow = null
  if (n > 0) {
    fast = headA
    slow = headB
  } else {
    n = length2 - length1
    fast = headB
    slow = headA
  }
  while(n > 0) {
    fast = fast.next
    n--
  }
  while (fast !== slow) {
    fast = fast.next
    slow = slow.next
  }
  return slow
};

var nodeLength = function (head) {
  var cur = head
  var n = 0
  while (cur !== null) {
    n += 1
    cur = cur.next
  }
  return n
}

方法2

  • 判断链表情况，其中有一个为空，则不能有公共结点，返回null。
  • 两个链表都从表头开始同步依次遍历。
  • 不需要物理上将两个链表连在一起，仅需指针在一个链表的尾部时直接跳到另一个链表的头部。
  • 根据上述说法，第一个相同的结点便是第一个公共结点；没有公共节点时，两个链表最终在末尾的空节点相遇。

Swift实现：

1
2
3
4
5
6
7
8
9
10
11
12
func getIntersectionNode2(_ headA: ListNode?, _ headB: ListNode?) -> ListNode? {
  if (headA === nil || headB === nil) {
    return nil
  }
  var l1 = headA
  var l2 = headB
  while (l1 !== l2) {
    l1 = l1 === nil ? headB : l1?.next
    l2 = l2 === nil ? headA : l2?.next
  }
  return l1
}

JavaScript实现：

1
2
3
4
5
6
7
8
9
10
11
12
var getIntersectionNode2 = function (headA, headB) {
  if (headA === null || headB === null) {
    return null
  }
  var l1 = headA
  var l2 = headB
  while (l1 !== l2) {
    l1 = l1 === null ? headB : l1.next
    l2 = l2 === null ? headA : l2.next
  }
  return l1
}