数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)

简介: 数据结构与算法⑥(第二章OJ题,下)后八道链表面试题

数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上):https://developer.aliyun.com/article/1513360


代码:

 
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1, lenB = 1;
    while (tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    while (tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    if (tailA != tailB)
    {
        return NULL;
    }
    int gap = abs(lenA - lenB);
    //gap 差值 abs求整数绝对值函数 头文件:stdlib.h
    while (gap--)
    {
        if (lenA > lenB)
        {
            headA = headA->next;
        }
        else if (lenB > lenA)
        {
            headB = headB->next;
        }
    }
    while (headA != headB)//注意不能比较next又返回next(可能为空)血的教训
    {
        headA = headA->next;
        headB = headB->next;
    }
    return headA;
}

评论区大诗人的代码:

(程序猿的浪漫)笑

//朋友们,请一定要珍惜身边的那个 ta 啊!你们之所以相遇,正是因为你走了 ta 走过的路,
//而 ta 也刚好走了你走过的路。这是何等的缘分!
//而当你们携手继续走下去时,你会慢慢变成 ta 的样子,ta 也会慢慢变成你的样子。
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (!headA || !headB) {
            return NULL;
        }
        ListNode *you = headA, *she = headB;
        while (you != she) { // 若是有缘,你们早晚会相遇
            you = you ? you->next : headB; // 当你走到终点时,开始走她走过的路
            she = she ? she->next : headA; // 当她走到终点时,开始走你走过的路
        }
        // 如果你们喜欢彼此,请携手一起走完剩下的旅程(将下面这个 while 块取消注释)。
        // 一路上,时而你踩着她的影子,时而她踩着你的影子。渐渐地,你变成了她,她也变
        //成了你。
        /* while (she) {
            you = she->next;
            she = you->next;
        } */
        return you;
    }
};

9. 判断链表中是否有环

141. 环形链表

难度简单

给你一个链表的头节点 head ,判断链表中是否有环。

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。

为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置

(索引从 0 开始)。注意:pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。


如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

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

输出:true

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

示例 2:

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

输出:true

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

示例 3:

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

输出:false

解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 10^4]
  • -10^5 <= Node.val <= 10^5
  • pos 为 -1 或者链表中的一个 有效索引

进阶:你能用 O(1)(即,常量)内存解决此问题吗?

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
 
}

暴力求解代码:

自己按照给的范围取巧写的代码:

看完别人的快慢指针和证明又是震惊的一天

bool hasCycle(struct ListNode* head) {
    struct ListNode* head1 = head, * head2 = head;
    int x = 10000, y = 10000;
    while (x-- && head1 && head2)
    {
        while (y-- && head2)
        {
            if (head2->next == head1)
            {
                return true;
            }
            head2 = head2->next;
        }
        head1 = head1->next;
        if (head2)
        {
            head2 = head;
        }
    }
    return false;
}

快慢指针代码:

就是在环里,下面走两步的快指针一定会追上慢指针

 bool hasCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        if (fast->next == slow)
        {
            return true;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}

为什么fast一定会和slow相遇呢?

为什么fast要走两步,slow走一步呢?

面试的时候不会让写代码,但会问下面的两个延伸问题

(图片拼起来的,看不清楚的话点开放大看吧,很重要)



10. 返回链表入环的第一个节点

142. 环形链表 II

难度中等

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

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

不允许修改 链表。

示例 1:


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

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

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

示例 2:

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

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

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

示例 3:

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

输出:返回 null

解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 10^4] 内
  • -10^5 <= Node.val <= 10^5
  • pos 的值为 -1 或者链表中的一个有效索引
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
 
}

公式+快慢指针代码:

首先要知道,根据上面的距离的递减,fast在slow进环后最多走两圈,slow最多走一圈。

fast就会追上slow。

以下是公式推导证明

所以根据公式L = (N - 1) * C + C * X

得出结论:一个指针从相遇点开始走,一个指针走表头开始走,他们会在环的入口点相遇。

(L是一个指针从表头开始走到入口点的距离,C * X 是相遇点往后走到表头的距离,相等,就相遇。)

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                meet = meet->next;//一个指针从相遇点走
                head = head->next;//一个指针从头走
            }
            return meet;//会在入环的第一个节点相遇
        }
    }
    return NULL;
}

另一种方法:转化成链表相交

如果要求不破坏链表长度,可以让head当尾,meet当头

数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下):https://developer.aliyun.com/article/1513376

目录
相关文章
|
1天前
|
机器学习/深度学习 算法 C语言
【C/数据结构与算法】:10道链表经典OJ
【C/数据结构与算法】:10道链表经典OJ
7 1
|
1天前
|
算法
【C/数据结构与算法】:二叉树经典OJ
【C/数据结构与算法】:二叉树经典OJ
8 0
【C/数据结构与算法】:二叉树经典OJ
|
1天前
|
存储 算法 前端开发
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
【C/数据结构与算法】:链表的实现(单向链表+双向链表)
4 0
|
1天前
数据结构篇:链表和树结构的操作方法
数据结构篇:链表和树结构的操作方法
2 0
|
3天前
|
Java Android开发 Kotlin
Android面试题:App性能优化之Java和Kotlin常见的数据结构
Java数据结构摘要:ArrayList基于数组,适合查找和修改;LinkedList适合插入删除;HashMap1.8后用数组+链表/红黑树,初始化时预估容量可避免扩容。SparseArray优化查找,ArrayMap减少冲突。 Kotlin优化摘要:Kotlin的List用`listOf/mutableListOf`,Map用`mapOf/mutableMapOf`,支持操作符重载和扩展函数。序列提供懒加载,解构用于遍历Map,扩展函数默认参数增强灵活性。
10 0
|
5天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之链表
Java数据结构与算法:线性数据结构之链表
|
8天前
|
存储 算法 Linux
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记
【内核链表】数据结构——深入理解内核链表的概念和操作&笔记
|
15天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
15天前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
20天前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
9 2