目录
- 删除链表中的节点
- 反转一个链表
- 递归实现
- 迭代（非递归）实现
- 判断一个链表是否有环
一 删除链表中的节点
237. 删除链表中的节点
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
说明:
链表至少包含两个节点。
链表中所有节点的值都是唯一的。
给定的节点为非末尾节点并且一定是链表中的一个有效节点。
不要从你的函数中返回任何结果。
- 实例代码如下
- (id)remove:(NSUInteger)index {
LinkNode *node = _first;
if (index == 0) {
_first = _first.next;
} else {
LinkNode *prev = [self node:index - 1];
node = prev.next;
prev.next = node.next;
}
self.size--;
return node.element;
}
运行结果如下：
image.png
二 反转一个链表
206. 反转链表
示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
请分别用迭代（非递归）或递归两种方式实现
公共代码说明
- 链表节点输出打印
- (NSString *)description {
[super description];
NSMutableString *strM = [NSMutableString string];
[strM appendString:[NSString stringWithFormat:@"[%@",self.element]];
LinkNode *node = self;
while (node.next) {
node = node.next;
[strM appendString:[NSString stringWithFormat:@",%@",node.element]];
}
[strM appendFormat:@"]"];
return strM.copy;
}
- 生成链表
LinkedList *list = [[LinkedList alloc] init];
self.list = list;
[list add:@1];
[list add:@2];
[list add:@3];
[list add:@4];
[list add:@5];
NSLog(@"%@",list.description);
递归实现实例代码如下
// 递归反转链表
- (LinkNode *)reverseList:(LinkNode *)head {
if (head == nil || head.next == nil) {
return head;
}
// 递归实现
LinkNode *newHead = [self reverseList:head.next];
head.next.next = head;
head.next = nil;
return newHead;
}
效果实现如下
递归实现.png
-
画图说明
image.png
递归解题说明.png
解释：即递归至找到最后一个节点，然后依次将每一次递归时的当前节点的next的next指向自己，即将
后一个节点的next指向自己。
迭代（非递归）实现实例代码如下
// 迭代(非递归)反转链表
- (LinkNode *)reverseList2:(LinkNode *)head {
if (head == nil || head.next == nil) {
return head;
}
LinkNode *newHead = nil;
while (head) {
LinkNode *tmp = head.next;
head.next = newHead;
newHead = head;
head = tmp;
}
return newHead;
}
运行效果如下：
image.png
- 画图说明
image.png
- 依次打印每一次循环后节点的链表值
image.png
- 每一次循环后图表分析
image.png
总结：通过一个临时节点
tmp，移动到下一个节点，然后将下一个节点的next指向自己即newHead。
三 判断一个链表是否有环
141. 环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
image.png
实例2
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
image.png
实例3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
image.png
- 实例代码如下
// 环形链表
- (bool)hasCycle:(LinkNode *)head {
if (head == nil || head.next == nil) {
return false;
}
LinkNode *slow = head;
LinkNode *fast = head.next;
while (fast != nil && fast.next != nil) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return fast;
}
- 测试代码如下
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view, typically from a nib.
LinkedList *list = [[LinkedList alloc] init];
self.list = list;
[list add:@1];
[list add:@2];
[list add:@3];
[list add:@4];
[list add:@5];
NSLog(@"%@",list.description);
// 环形链表
LinkNode *lastNode = list.last;
// lastNode.next = list.first.next;
// NSLog(@"%@",list.first.description); // 不打印,因为一直在循环中
bool hasCycle = [self hasCycle:list.first];
NSLog(@"是否有环:%d",hasCycle);
}
运行结果如下：
无环.png
加上 lastNode.next = list.first.next;句代码后打印结果如下：
image.png
四 复杂度分析
4.1 动态数组，链表复杂度分析
image.png
4.2 动态数组add(E element)复杂度分析
- 最好 ：O(1)
- 最坏：O(n)
- 平均：O(1)
- 均摊：O(1)
画图分析
image.png
什么情况下适合使用均摊复杂度？
经过连续的多次复杂度比较低的情况后，出现个别复杂度比较高的情况
本文会持续更新中，更多精彩内容敬请期待。
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏点赞是对我最大的支持和鼓励，欢迎点赞打赏。
