给定一个链表旋转链表,将链表每个节点向右移动 k 个位置其中 k 是非负数。
——————————————————————————————————————————————————————
本题可以通过多次遍历、额外数组存储空间等方法来实现
这里分享一个空间复杂度为O(1),时间复杂度为O(n)的方法(n为链表长度)。
惯例我会先申请一个空节点resHead作为新链表的头节点,那么整个返回节点指向:resHead->next
首先一趟遍历得到链表长度l,然后將原单链表改造成为循环链表,并记录下链表最后一个节点的位置为resEnd;
然后计算offset = k%l,把旋转的数值控制到n以内;
最后根据计算的offset,移动head和resEnd节点移動步数为l-offset,注意这一步很关键因为旋转可以看作是找头节点和尾节点,比如k=2就是要找倒数第二个节点作为头节点,倒数第3个作为尾节點通过计算后可以得到:head移动l-offset为新的头,resEnd为新的尾