目录
- 删除链表中的节点
- 反转一个链表
- 递归实现
- 迭代(非递归)实现
一 删除链表中的节点
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
解释:即递归至找到最后一个节点,然后依次将每一次递归时的当前节点的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- 画图说明
- 依次打印每一次循环后节点的链表值
- 每一次循环后图表分析
总结:通过一个临时节点
tmp
,移动到下一个节点,然后将下一个节点的next
指向自己
即newHead
。
本文会持续更新中,更多精彩内容敬请期待。
本文参考 MJ老师的 恋上数据结构与算法
本人技术水平有限,如有错误欢迎指正。
书写整理不易,您的打赏点赞是对我最大的支持和鼓励,欢迎点赞打赏。
网友评论