关于亚麻OA1 shoppingcart这道题目

大家好，我做亚麻OA时有一道shopping cart链表的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

轮VO，面试的时候要和面试官讲解我的代码，如果这个方法不符合要求该怎么办啊？

希望大家解答，谢谢！

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

类似情况，蹲一个。写题的时候也纠结了很久，是要求O（1）空间，还是要求不能创建新node（dummy/sentinel），还是要求不能用任何额外空间（毕竟栈空间也算memory）。如果是任何额外空间都不能用的话，那就不能用tail指针，这题就没法O（N）地做出来，我觉得不合理；如果是不能用dummy node但是可以用临时变量，那可以用头指针代替dummy node，但我感觉实际上没啥差...

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

个人想法，这题不让用额外空间大概只是不想让我们创建额外节点，比如dummy node这种。多一个变量应该无所谓的吧

井上拓 发表于 2022-8-24 09:50
个人想法，这题不让用额外空间大概只是不想让我们创建额外节点，比如dummy node这种。多一个变量应该无所谓 ...

dummy node应该也不算额外空间吧 那只是一个reference 如果用stack保存node才算

井上拓 发表于 2022-8-24 06:50
个人想法，这题不让用额外空间大概只是不想让我们创建额外节点，比如dummy node这种。多一个变量应该无所谓 ...

感谢回复已加米，我在地里看到一些其他的解法用了dummy node，我一会把代码发出来，大家可以讨论一下

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

贴上两个地里看到的其他解法，都是用了dummy node

匿名用户 发表于 2022-8-24 10:06
感谢回答已加米，那么请问我的做法用length存储节点个数，算额外空间嘛😂？ 题目的要求除了创建新 ...

请问楼主是只用length不用头/尾指针也不用dummy node吗，好奇是怎么做到的

匿名用户 发表于 2022-8-24 10:21
请问楼主是只用length不用头/尾指针也不用dummy node吗，好奇是怎么做到的

不，我是用了一个length，还有一个尾指针tail

匿名用户 发表于 2022-8-24 10:23
不，我是用了一个length，还有一个尾指针tail

那其实尾指针和length都是一样的栈上变量吧。。我感觉至少尾指针肯定省不了，不然没法每个操作都O(1)