当前位置:   article > 正文

【Leetcode刷题记录_C++】【链表】_c++给定 n个数据,请你先建立头节点 head的单链表,然后两两交换其中相邻的节点,并

c++给定 n个数据,请你先建立头节点 head的单链表,然后两两交换其中相邻的节点,并

链表

删除节点时,经常会因为对当前节点进行操作而导致内存或指针出现问题。有两个小技巧可以解决这个问题:一是尽量处理当前节点的下一个节点而非当前节点本身,二是建立一个虚拟节点 (dummy node),使其指向当前链表的头节点,这样即使原链表所有节点全被删除,也会有一个 dummy 存在,返回 dummy->next 即可。

链表的基本操作

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
思路:
head后移:

ListNode *prev = nullptr, *next;
while (head) {
	next = head->next;
	head->next = prev;
	prev = head;
	head = next;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

代码:

24. 两两交换链表中的节点

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
思路:
p = head;
while(p&&p->next){
n=p->next;
p->next=n->next;
n->next=p;
p=p->next;
}

代码:

其它链表技巧

160. 相交链表

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

图示两个链表在节点 c1 开始相交:
在这里插入图片描述

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

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

思路:
设链表1到相交的距离为a,链表2为b,相交点到终点距离为c,那么控制两个指针从两个头出发,当其中一个到达了终点后,把它放到另一条链表的头,最终两个在走过a+b+c后会相遇在相交点
代码:

234. 回文链表

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

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

思路:
①复制到数组用双指针
②先使用快慢指针找到链表中点,再把链表切成两半;然后把后半段翻转;最后比较两半是否相等
③递归:指到尾节点与头对比,返回上一层
**代码:**4

练习

83. 删除排序链表中的重复元素

存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除所有重复的元素,使每个元素 只出现一次 。

返回同样按升序排列的结果链表。
思路:
next到下一个不重复的节点
代码:

328. 奇偶链表

给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL

示例 2:

输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
思路:
a->next=b->next;
b->next=a->next;

最后连接
代码:

19. 删除链表的倒数第 N 个结点

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

进阶:你能尝试使用一趟扫描实现吗?
思路:
①类似找中点:first 比 second超前 n 个节点。当 first 遍历到链表的末尾时,second 就恰好处于倒数第 n 个节点。

②递归回溯(栈)
代码:

148. 排序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

进阶:

你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
  • 1

思路:
二分归并
分割 cut 环节: 找到当前链表中点,并从中点将链表断开(以便在下次递归 cut 时,链表片段拥有正确边界);

我们使用 fast,slow 快慢双指针法,奇数个节点找到中点,偶数个节点找到中心左边的节点。
找到中点 slow 后,执行 slow.next = None 将链表切断。
递归分割时,输入当前链表左端点 head 和中心节点 slow ....的下一个节点 tmp(因为链表是从 slow 切断的)。
cut 递归终止条件: 当head.next == None时,说明只有一个节点了,直接返回此节点。
  • 1
  • 2
  • 3
  • 4

合并 merge 环节: 将两个排序链表合并,转化为一个排序链表。

双指针法合并,建立辅助ListNode h 作为头部。
设置两指针 left, right 分别指向两链表头部,比较两指针处节点值大小,由小到大加入合并链表头部,指针交替前进,直至添加完两个链表。
返回辅助ListNode h 作为头部的下个节点 h.next。
时间复杂度 O(l + r),l, r 分别代表两个链表长度。
  • 1
  • 2
  • 3
  • 4

当题目输入的 head == None 时,直接返回None。

在这里插入图片描述

代码:

本文内容由网友自发贡献,转载请注明出处:https://www.wpsshop.cn/w/代码世界探险家/article/detail/61231
推荐阅读
相关标签
  

闽ICP备14008679号