改正。 空间复杂度是N。另回答问题

dannyp (Danny)
我想我的解法有问题。但是我看了一下别人的解发,发现还没有我的好。
我的解法的问题在于在不改变链表的情况下,空间复杂度为K*N(K为常数), 但是若允许改变链表,则空间复杂度为1(直接修改原链表的DATA)。
不过直接修改原链表,虽然原题没有限制,但近似无赖的行为了。
真的远不如MS的办法巧妙。
不过不知道有没有人能顺着我的思路再走一步,将空间复杂度减少到与N无关?
(关于空间复杂度不能与N发生关系,我认为原题并没有限制,因为MS的解法时间复杂度也为2*N,若N为无穷,时间也为无穷。)
射日兄,对,新链表NEXT=旧链表的NEXT,而旧链表的NEXT指向新链表的THIS,当算法完毕时再将旧链表的指针根据新链表的指针值修改回去即可
(#144572@0)
2001-7-25 -05:00

回到话题: 看了#142300,也来贴一道MS研究所在中国招聘的考题......

回到论坛: HOME枫下论坛枫下论坛主坛工作学习IT技术讨论

URL:   
http://www.rolia.net/zh/post.php?f=0&p=144572