不仅游戏会坑人，来看看LeetCode出题人是怎么埋坑的
今天是LeetCode专题的第35篇文章，上一篇文章当中我们一口气肝了三题，不知道大家感觉怎么样？今天我们来放松一下，看一道相对比较简单也比较有趣的问题。
题意
这题的题意也只有一句话，秉承了LeetCode一贯题狠话不多的风格。
题意是给定一个链表和一个整数K，要求将链表当中的所有元素向右移动K位。
注意这里，元素往右边移动的意思并不是删除了，移动出边界的元素会放置到最左边。
样例
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
出题人的阴谋
在我们正式开始做题之前，先来说点题外话。如果大家玩过一些著名的硬核动作游戏，比如黑魂、只狼、仁王等等，会发现这些游戏当中都有一个惯用的套路，就是墙角怪。
我没找到合适的游戏截图，就来自己手动画一张。
这个套路其实并不高明，说白了就是在显眼的地方放一个宝物，玩家瞥一眼就会看到。但是在玩家视野的盲区会藏一个怪物，如果玩家贸贸然去捡这个宝物，那么怪物就会冲上来给玩家致命一击，把玩家阴死。
这其实利用的人们的直线思维，也就是本能反应。
当你明白了这个道理之后，你会发现不仅仅是游戏，很多问题就是利用人们的直线思维来困住我们。比如这题，也藏着一个出题人故意挖的坑。
我们来仔细看一下，这题的题意非常明显，我们一眼看完就能想到解法。其实这个就相当于游戏中的宝物，玩家看到宝物的第一反应就是去捡，同样，我们想出解法之后的第一反应就是去编码。那么这样直线思维的结果就是被阴。
那么阴我们的“怪物”在哪呢？就藏在我们思维的盲区处，在这题当中，我们思维的盲区就是K。我们就觉得这是一个普通的整数就放过了，往往不会多想。就好像游戏里的墙角，我们本能地觉得墙角后面没有东西一样。但其实出题人并没有给出K的范围，这个K可能会很大，大到我们无法在规定的时间内遍历完。
所以如果我们贸贸然上去用模拟的方法一个一个地移动链表的话，结果就是被阴，测试的时候样例全都通过，但是一提交就TLE（time limited exceed），也就是超时。
如果你做多了题目，可能会很容易发现这个坑，但是还有另外一个坑等着你。这个坑相比之下更加阴险，也就是说出题人其实在墙角藏了两只怪，K只是其中比较明显的那只。那么另外一只怪是什么呢？
另外一只怪就是我们的这个链表了，有谁规定了这个链表一定是有元素的？如果链表本身就是空的怎么办？
这个时候你用K对n取模就会报错，因为n不能为0。在LeetCode当中还好，我们提交一次看到报错的数据也就知道了。但如果是线上的算法比赛，很有可能会坑掉你很多时间去debug。虽然我饱经锻炼，但是有时候不小心还是会踩坑。
所以我们做题的时候需要冷静下来思考一下，尤其要小心变量的范围，往往当中藏着巨坑。
题解
其实这题识破了这个坑之后就基本上没有难度了，解决K范围的方法也很简单。对于长度为n的链表而言，如果它这样移动n次相当于回到原点。那么我们直接用K对n取模，得出的余数才是我们真正需要移动的距离。
我们可以开辟一个数组，先把链表中的元素全部另外存储一遍，自己重新构造新的链表进行返回，也可以模拟链表的移动过程，在原链表上操作。这两种方法都是可以的，我们一种一种来看代码。
我们先来看第一种做法的代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
pnt = head
elements = []
# 直接遍历链表，把元素全部存在list中
while pnt is not None:
elements.append(pnt.val)
pnt = pnt.next
n = len(elements)
if n == 0:
return pnt
k %= n
# 通过切片，我们可以很方便地实现移动操作
elements = elements[n-k:] + elements[:n-k]
head = ListNode()
pnt = head
# 重新构建链表返回即可
for e in elements:
cur = ListNode(e)
pnt.next = cur
pnt = cur
return head.next
如果操作链表的话速度会快很多，因为我们节省了开辟内存以及切片元素的开销。但是相比于上面这种写法会复杂一些，因为我们移动链表本质上是将链表切分成了两个部分，然后再调换顺序拼接到一起。
但是这里有一个坑，如果k=0的时候，链表是切分不出来两个部分的，所以对于这种情况需要单独判断。好在k=0的时候也简单，k=0说明不需要移动，那么我们直接返回即可。
由于链表操作非常琐碎，所以整个代码可读性不佳，这也是很多大神讨厌使用链表的原因。我们来看下代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
pnt = head
n = 0
# 计算链表长度
while pnt is not None:
n += 1
pnt = pnt.next
if n == 0:
return pnt
k %= n
if k == 0:
return head
pnt = head
# 链表向右移动k个元素，其实是把倒数k个元素放到头部
# 也就是说头部的元素是n-k个
for i in range(n-k-1):
pnt = pnt.next
cur = pnt.next
pnt.next = None
pnt = cur
# 将末尾的元素接到头部
while pnt.next is not None:
pnt = pnt.next
pnt.next = head
return cur
结尾与升华
到这里，这道题就算是完整讲完了。
很多人觉得算法题很难，acm更难，这些算法比赛难除了算法本身的困难之外，还有很大的一部分原因就在这里了。出题人在题目当中埋坑设置trick是非常普遍的做法，像是著名的codeforces和topcoder比赛甚至开创了互相hack的机制。
也就是让选手们互相阅读对方的代码，发现对方中招的话，就构造数据去hack掉对方的解答。一旦hack成功就能获得大量的分数奖励，所以高阶选手除了能够享受比赛本身的乐趣之外，还可以体验一把竞技游戏的感觉。据说楼教主有一次就是因为比赛结束之前，接连hack成功逆袭夺冠的。
和一些硬核游戏一样，算法做题本身的正反馈其实是很足的。只是前期的门槛比较高，很多人迈不过去。这时候除了多做多练提升自己的水平之外，也要学会摸清楚出题人的套路，既可以增加成功率，也会找到新的乐趣。
今天的文章就到这里，原创不易，扫码关注我，获取更多精彩文章。