【随想】每日两题Day.7

简介: 【随想】每日两题

题目:面试题 02.07.链表相交

给你两个单链表的头节点 headAheadB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null

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

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

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

示例 1:

输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3

输出:Intersected at '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

输出:Intersected at '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 。

提示:


listA 中节点数目为 m

listB 中节点数目为 n

0 <= m, n <= 3 * 104

1 <= Node.val <= 105

0 <= skipA <= m

0 <= skipB <= n

如果 listA 和 listB 没有交点,intersectVal 为 0

如果 listA 和 listB 有交点,intersectVal == listA[skipA + 1] == listB[skipB + 1]

进阶:你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?


代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA != null) {
            lenA++;
            curA = curA.next;
        }
        while(curB != null) {
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        int count = 0;
        if(lenA > lenB) {
            count = lenA - lenB;
            for(int i = 0;i<count;i++) {
                curA = curA.next;
            }
        }else {
            count = lenB - lenA;
            for(int i = 0;i<count;i++) {
                curB = curB.next;
            }
        }
        while(curA != curB && curA != null && curB != null) {
            curA = curA.next;
            curB = curB.next;
        }
        if(curA == null || curB == null) return null;
        return curA;
    }
}

思考:

遍历 链表A、B计算出长度差count,让长的先走count步,然后同步走一一比较。

题目:142.环形列表Ⅱ

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。


如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。


不允许修改 链表。


示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。


示例 2:

示例 3:

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

提示:


链表中节点的数目范围在范围 [0, 104] 内

-105 <= Node.val <= 105

pos 的值为 -1 或者链表中的一个有效索引

进阶:你是否可以使用 O(1) 空间解决此题?


代码:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return null;
        ListNode fast = head.next.next;
        ListNode slow = head.next;
        while(fast != slow && fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        if(fast == null || fast.next == null) return null;
        ListNode cur1 = fast;
        ListNode cur2 = head;
        while(cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }
}

思考:(重要)

这个题需要一些数学推理。经推理后的结论,定义 fast 和 slow 两个结点,fast一步走两个 ,slow一步走一个。若有环,fast和slow一定在环中相遇。那么怎么找到环的入口呢?就是让cur1在head开始走,cur2在fast、slow相遇结点开始走,当cur1 == cur2 时,此时就是环的入口!


目录
相关文章
|
21天前
|
数据安全/隐私保护
【随想】每日两题Day.14
【随想】每日两题Day.14
17 0
|
21天前
【随想】每日两题Day.17
【随想】每日两题Day.17
23 0
|
21天前
【随想】每日两题Day.2
随想】每日两题Day.2
9 0
|
21天前
|
算法
【随想】每日两题Day.9
【随想】每日两题
19 1
|
21天前
【随想】每日两题Day.4
【随想】每日两题Day.4
18 0
|
21天前
【随想】每日两题Day.18
【随想】每日两题Day.18
23 0
|
21天前
|
算法
【随想】每日两题Day.15
【随想】每日两题Day.15
21 0
|
21天前
【随想】每日两题Day.19
【随想】每日两题Day.19
18 0
|
21天前
|
算法
【随想】每日两题Day.1
【随想】每日两题Day.1
19 0
|
21天前
【随想】每日两题Day.8
【随想】每日两题
16 0