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

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

6. 分割链表成两部分

面试题 02.04. 分割链表

难度中等

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,

使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你不需要 保留 每个分区中各节点的初始相对位置。

示例 1:

输入:head = [1,4,3,2,5,2], x = 3

输出:[1,2,2,4,3,5]

示例 2:

输入:head = [2,1], x = 2

输出:[1,2]

提示:

  • 链表中节点的数目在范围 [0, 200] 内
  • -100 <= Node.val <= 100
  • -200 <= x <= 200
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* partition(struct ListNode* head, int x){
 
}

这题在牛客上标注较难,多了一个限制条件,且没有C语言提交的方式,但C++兼容C,用C++交就行

CM11 链表分割 链接:链表分割_牛客题霸_牛客网 (nowcoder.com)

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

哨兵位头结点+尾插代码:

struct ListNode* partition(struct ListNode* head, int x) {
    //开哨兵位头节点 方便尾插
    struct ListNode* small_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    small_head->next = NULL;
    struct ListNode* large_head = (struct ListNode*)malloc(sizeof(struct ListNode));
    large_head->next = NULL;
    struct ListNode* small_tail = small_head;
    struct ListNode* large_tail = large_head;
    while (head)
    {
        if (head->val < x)
        {
            small_tail->next = head;
            small_tail = small_tail->next;
        }
        else
        {
            large_tail->next = head;
            large_tail = large_tail->next;
        }
        head = head->next;
    }
    large_tail->next = NULL;//易忘记 可能成环
    small_tail->next = large_head->next;
    struct ListNode* new_head = small_head->next;
    free(small_head);//临时指针可以不置空
    free(large_head);
    return new_head;
}

7. 链表的回文结构

234. 回文链表

剑指 Offer II 027. 回文链表

(这两题是一模一样的)

难度简单


给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;

否则,返回 false 。

示例 1:


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

输出:true

示例 2:

输入:head = [1,2]

输出:false

提示:

  • 链表中节点数目在范围[1, 10^5] 内
  • 0 <= Node.val <= 9

进阶:你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

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

这题也在牛客上标注较难

OR36 链表的回文结构 链接:链表的回文结构_牛客题霸_牛客网 (nowcoder.com)

描述

对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。

给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。保证链表长度小于等于900。

测试样例:

1->2->2->1

返回:true

快慢指针+反转代码:

这题可以根据给的范围开出最大范围的数组,空间也是O(1)然后用数组判断回文,但不建议这么做

可以直接用前五道写过的找中间节点和反转函数的函数,但不熟还是要多写

画图发现如果不解链表的话也能找到终止条件

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newHead = NULL, * cur = head;
    while (cur)
    {
        struct ListNode* curNext = cur->next;
        cur->next = newHead;//头插
        newHead = cur;//迭代往后走
        cur = curNext;
    }
    return newHead;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head, * slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;//快指针一次走两步
        slow = slow->next;//慢指针一次走一步
    }
    return slow;
}
bool isPalindrome(struct ListNode* head) {
    struct ListNode* mid = middleNode(head);
    struct ListNode* reverse_mid = reverseList(mid);
    while (head && reverse_mid)
    {
        if (head->val != reverse_mid->val)
        {
            return false;
        }
        else
        {
            head = head->next;
            reverse_mid = reverse_mid->next;
        }
    }
    return true;
}

8. 找两个链表的第一个公共结点

160. 相交链表

面试题 02.07. 链表相交

剑指 Offer 52. 两个链表的第一个公共节点

(链接题目都是一样的,给这么多链接只是为了知道这题在很多地方出现)

难度简单

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

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


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

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

自定义评测:

评测系统 的输入如下(你设计的程序 不适用 此输入):

  • intersectVal - 相交的起始节点的值。如果不存在相交节点,这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中(从头节点开始)跳到交叉节点的节点数
  • skipB - 在 listB 中(从头节点开始)跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案


示例 1:

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

输出:Intersected at '8'

解释:相交节点的值为 8 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,6,1,8,4,5]。


在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。


— 请注意相交节点的值不为 1,因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说,它们在内存中指向两个不同的位置,而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点,B 中第四个节点) 在内存中指向相同的位置。

示例 2:

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

输出:Intersected at '2'

解释:相交节点的值为 2 (注意,如果两个链表相交则不能为 0)。

从各自的表头开始算起,链表 A 为 [1,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
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点,intersectVal 为 0
  • 如果 listA 和 listB 有交点,intersectVal == listA[skipA] == listB[skipB]

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    
}

思路1 :暴力求解-穷举

依次取A链表中的每个节点跟B链表中的所有节点比较

如果有地址相同的节点,就是相交,返回第一个相同的交点

时间:O(N^2) 不符合题意

思路2: 时间要求优化到O(N)

1、尾节点相同就是相交,否则就不相交

2、求交点:长的链表先走(长度差)步,再同时走,返回第一个相同的交点

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

目录
相关文章
|
20天前
|
消息中间件 算法 Java
抖音面试:说说延迟任务的调度算法?
Netty 框架是以性能著称的框架,因此在它的框架中使用了大量提升性能的机制,例如 Netty 用于实现延迟队列的时间轮调度算法就是一个典型的例子。使用时间轮调度算法可以实现海量任务新增和取消任务的时间度为 O(1),那么什么是时间轮调度算法呢?接下来我们一起来看。 ## 1.延迟任务实现 在 Netty 中,我们需要使用 HashedWheelTimer 类来实现延迟任务,例如以下代码: ```java public class DelayTaskExample { public static void main(String[] args) { System.ou
27 5
抖音面试:说说延迟任务的调度算法?
|
4天前
链表OJ题
链表OJ题
23 8
|
1天前
|
机器学习/深度学习 算法 C语言
【C/数据结构与算法】:10道链表经典OJ
【C/数据结构与算法】:10道链表经典OJ
7 1
|
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
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
15天前
|
存储 算法 大数据
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
深入解析力扣170题:两数之和 III - 数据结构设计(哈希表与双指针法详解及模拟面试问答)
|
15天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
15天前
|
存储 算法 数据挖掘
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
数据结构面试常见问题:解锁10大关键问题及答案解析【图解】
|
19天前
|
存储 关系型数据库 MySQL
万字详细面试被吊打的总结(SE->数据结构->MYSQL)
万字详细面试被吊打的总结(SE->数据结构->MYSQL)
|
1天前
|
算法
基于GA遗传优化的混合发电系统优化配置算法matlab仿真
**摘要:** 该研究利用遗传算法(GA)对混合发电系统进行优化配置,旨在最小化风能、太阳能及电池储能的成本并提升系统性能。MATLAB 2022a用于实现这一算法。仿真结果展示了一系列图表,包括总成本随代数变化、最佳适应度随代数变化,以及不同数据的分布情况,如负荷、风速、太阳辐射、弃电、缺电和电池状态等。此外,代码示例展示了如何运用GA求解,并绘制了发电单元的功率输出和年变化。该系统原理基于GA的自然选择和遗传原理,通过染色体编码、初始种群生成、适应度函数、选择、交叉和变异操作来寻找最优容量配置,以平衡成本、效率和可靠性。