讲真，线性表中的元素进行逆置这个问题，就像是程序员新手村门口的第一个小Boss。看着不起眼，但每年，真的，每年都有无数新人倒在它面前。它不难，真的不难，但它就像一面镜子，能照出你对数据结构最基本、最朴素的理解到底有几斤几两。
你可能会觉得，不就是倒过来吗？12345变成54321，我用脚趾头都能想明白。没错，思路很简单，但实现它的“姿势”可就千差万别了。不同的姿势，背后是你代码的效率、空间感和思维的广度。
咱们先聊聊最耿直，也最容易想到的办法。
想象一下，你要整理一书架的书，想把顺序完全颠倒。最笨的办法是啥？找一块空地，把书架上最后一本书拿下来，放到空地的第一个位置；再拿倒数第二本，放到空地第二个位置……直到把整个书架搬空，空地上就出现了一个顺序完全相反的新书架。
这就是第一种解法：开辟一个全新的数组。
这个办法的逻辑简直不要太清晰。创建一个和原来线性表大小一模一样的新表。然后，从头到尾遍历原来的表（设索引为i），把取出的元素a[i]，放到新表的b[n-1-i]这个位置上。简单粗暴，逻辑清晰，写出来的代码，估计连实习生都能一眼看懂。但它的问题也和它的优点一样突出——浪费。你凭空多用了一倍的存储空间。如果这个线性表巨大无比，有好几百万个元素，你的内存可能直接就跟你“抗议”了。这就是典型的空间换时间，在某些场景下无可厚逼，但面试官看到你只写出这个，估计心里会默默叹口气，觉得你“思路有，但不够巧”。
那有没有更“巧”的办法呢？当然有，而且这才是这道题的精髓所在。
这就是大名鼎鼎的原地逆置，靠的是双指针法。
这个玩法就高级了。还是那个书架，这次我们不找空地了，就在这个书架上直接操作。我们派出两个“哨兵”，一个叫left，站在书架的最左边（第一个位置）；另一个叫right，站在书架的最右边（最后一个位置）。
然后，一声令下，left手里的书和right手里的书，交换！
就这么简单，一次交换，头和尾就换好了位置。然后呢？left向右走一步，right向左走一步，他俩碰头前，继续重复这个“交换”的动作。第二个和倒数第二个换，第三个和倒-数第三个换……
什么时候停下来？当left和right两个“哨兵”擦肩而过，或者在中间胜利会师的时候，整个逆置过程就宣告结束。整个过程，我们没有借助任何额外的存储空间（除了那个用于交换的临时变量），所有的操作都在原始的线性表内部完成。这叫什么？这就叫优雅！空间复杂度O(1)，这才是大多数面试官心中期待的答案。它考察的，就是你能不能在有限的资源里，把事情办得漂漂亮亮。
是不是就这两种了？别急，我们还能换个赛道玩。
有一种数据结构，它的特性简直是为“逆置”这个词量身定做的，那就是栈。
栈，你可以把它想象成一个只有一个开口的死胡同，或者一个羽毛球筒。它的核心特性就是后进先出 (LIFO)。你最后一个放进去的东西，必然是第一个被取出来的。
这不就巧了吗？
我们可以把线性表里的元素，从第一个开始，挨个儿地“压”进一个栈里。1、2、3、4、5，依次入栈。那么在栈里，5在最上面，1在最底下。
接下来，我们再把栈里的元素一个个“弹”出来，放回原来的线性表里。第一个弹出来的是谁？是5！第二个呢？是4！……最后一个弹出来的一定是1。你看，这么一进一出，顺序自然而然就颠倒了。
这个方法在思路上非常取巧，它巧妙地利用了栈这个数据结构的天然属性来解决问题。虽然它也需要额外的空间来存储这个栈（空间复杂度和第一种方法类似），但它展示的是一种完全不同的解题思路。它告诉你，解决问题不只有一条路，有时候换个工具，整个世界都会变得不一样。这在更复杂的算法问题中，是一种非常宝贵的思维方式。
所以你看，一个简单的线性表中的元素进行逆置，就能牵扯出三种截然不同的解法，背后是空间与时间的权衡、是原地操作的精妙、是数据结构特性的巧妙利用。代码的世界里，很多时候并没有唯一的标准答案，只有在特定场景下的最优解。而你，需要做的，就是把这些“兵器”都收入囊中，等到需要的时候，能信手拈来。
发表回复