LeetCode 160. Intersection of Two Linked Lists
Description
Write a program to find the node at which the intersection of two singly linked lists begins.
For example, the following two linked lists:
begin to intersect at node c1.
Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
Example 2:
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
Example 3:
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
Notes:
If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
描述
編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。
思路
- 這道題有兩種不同的寫法遥诉，其基本思路是一致的.
- 在上面的示例中，相交的節(jié)點(diǎn)我們稱之為c奖磁，如果c點(diǎn)前面A，B鏈表的節(jié)點(diǎn)個(gè)數(shù)是相同的繁疤，那么我們從A咖为，B的起點(diǎn)同時(shí)往后走，就一定會(huì)相遇.
- 于是我們就要想辦法把相交的節(jié)點(diǎn)前面節(jié)點(diǎn)數(shù)目變得一樣.
- 方法一稠腊，我們分別獲取鏈表A和鏈表B的長(zhǎng)度lena和lenb躁染，我們讓其中較長(zhǎng)的鏈表先走lena-lanb步(A比B長(zhǎng)，如果B更長(zhǎng)就是lenb-lena步)架忌，然后讓兩個(gè)鏈表同時(shí)往后面走.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-16 09:55:59
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-16 10:10:29
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB: return None
# 獲取鏈表的長(zhǎng)度
lena, lenb = self._lenList(headA), self._lenList(headB)
a, b = headA, headB
# 移動(dòng)起始位置到節(jié)點(diǎn)個(gè)數(shù)相同的第一個(gè)點(diǎn)
if lena > lenb:
for _ in range(lena - lenb):
a = a.next
elif lenb > lena:
for _ in range(lenb - lena):
b = b.next
# 同時(shí)往后面走
while a != b:
a, b = a.next, b.next
return a
# 輔助函數(shù)吞彤，獲取鏈表的長(zhǎng)度
def _lenList(self, Node):
res = 0
while Node:
res += 1
Node = Node.next
return res
- 方法二，為了獲得相同個(gè)數(shù)的鏈表個(gè)數(shù)的效果叹放，我們可以把鏈表A添加到鏈表B上饰恕，把鏈表B添加到鏈表B上.
- 體現(xiàn)的形式是先從鏈表A出發(fā)的節(jié)點(diǎn)如果走完了鏈表A，就接著鏈表B開始走井仰，反過(guò)來(lái)先從鏈表B出發(fā)的鏈表也一樣.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-16 09:55:59
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-16 10:10:29
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def getIntersectionNode(self, headA, headB):
"""
:type head1, head1: ListNode
:rtype: ListNode
"""
if not headA or not headB:
return None
a, b = headA, headB
# 另一種寫法埋嵌，為了達(dá)到從相同個(gè)數(shù)啟起點(diǎn)，我們把a(bǔ)鏈表添加到b鏈表前面
# 把b鏈表添加到a鏈表前面
while a != b:
if not a:
a = headB
elif not b:
b = headA
else:
a, b = a.next, b.next
return a
源代碼文件在這里.
?本文首發(fā)于何睿的博客俱恶，歡迎轉(zhuǎn)載雹嗦，轉(zhuǎn)載需保留文章來(lái)源拌喉，作者信息和本聲明.
