目录
160-相交链表
访问量:655
一、题目
地址:https://leetcode.com/problems/intersection-of-two-linked-lists/submissions/
编写一个程序,找到两个单链表相交的起始节点。
注意:
如果两个链表没有交点,返回 null.
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
交点,不是当前节点的值相同,而是两个节点的地址相同。
二、解法
1、解法一
思路:以其中一个链表headbB为主,另外一个链表headbA循环。从headbB中第一个节点开始,逐次判断,是否满足要求。
func getIntersectionNode(headA, headB *ListNode) *ListNode { if headB ==nil || headA == nil { return nil } var p0, pA, pB *ListNode pA = headA pB = headB for { if pB == nil { break } if pA == nil { pA = headA pB = pB.Next } if pA != pB { p0 = nil } else { pB = pB.Next if p0 == nil { p0 = pA } } pA = pA.Next } return p0 }
1、解法二
思路:如果链表是双向链表,那么这道题目就会变得特别简单,因为我们可以从后往前比较,可惜,不是哈。但是我们可以先计算链表长度,然后排除不需要比较的部分,如下图,链表1,前面一部分是不需要比较的。
func getIntersectionNode(headA, headB *ListNode) *ListNode { if headB ==nil || headA == nil { return nil } pA := headA pB := headB var i,j int for pA != nil { i ++ pA = pA.Next } for pB != nil { j ++ pB = pB.Next } var k int // pA 为长链, pB为短链 if i >= j { pA = headA pB = headB k = i - j } else { pA = headB pB = headA k = j -i } for k > 0 { pA = pA.Next k-- } for pA != pB { if pA == nil || pB == nil { break } pA = pA.Next pB = pB.Next } return pA }
本文为原创文章,请尊重辛勤劳动,如需转载,请保留本文地址
若您感觉本站文章不错,读后有收获,不妨赞助一下?
我要赞助