1回答

liuyubobobo

2021-03-25

1

使用哈希表。本质是给每一个字符串计算一个哈希值，在遇到哈希冲突的时候再检测两个字符串是否相等。注意，哈希表可以存储（哈希值，字符串索引）的数据对，而不需要把字符串重新存一份（如果字符串长度很长，这是很耗空间的）。

关于字符串的哈希值，可以参考这个课程哈希表的部分（大部分语言自己有自己内部的实现，比如 Java.）

2

你确定问题需要两个栈吗？因为对一个链表进行翻转，两个指针遍历一遍链表就够，根本不需要栈，反而是额外的空间耗费。

参考代码（Java）：https://github.com/liuyubobobo/Play-with-Algorithm-Interview/blob/master/05-About-Linked-List/Course%20Code%20(Java)/01-Reverse-Linked-List/src/Solution1.java

对应 Leetcode 206 号问题。

即使需要栈，一个栈就够，相当于是模拟递归翻转的过程。理解起来也很简单，所有节点一次入栈，然后出栈以后出栈的节点的 next 指向栈顶的节点就好。入栈再出栈，所有节点已经反序了，只需要确保 next 的链接就好了。

继续加油！：）

0

hiuyubobobo

回复

horeverLovel

hp>我说的两个指针的方法完全不需要栈。

h021-03-25

共2条回复