1. 题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:

  1. 输入: 1->2->3->4->5->NULL, k = 2
  2. 输出: 4->5->1->2->3->NULL
  3. 解释:
  4. 向右旋转 1 步: 5->1->2->3->4->NULL
  5. 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

  1. 输入: 0->1->2->NULL, k = 4
  2. 输出: 2->0->1->NULL
  3. 解释:
  4. 向右旋转 1 步: 2->0->1->NULL
  5. 向右旋转 2 步: 1->2->0->NULL
  6. 向右旋转 3 步: 0->1->2->NULL
  7. 向右旋转 4 步: 2->0->1->NULL

2. 解题思路

对于这道题目，一个很直接的思路就是将单链表转化为一个环形链表，然后移动完成之后再将链表断开为单链表，实现步骤主要是三步：

  • 首先遍历链表，找到链表的尾结点，将尾结点和头结点连起来，这样就形成了一个环形链表；
  • 题目说的右移k步，这里我们让尾结点左移，相当于往左移动length-k步；
  • 最后，移动完成之后，找到链表的尾结点，将环形链表断开为-单向链表。

复杂度分析：

  • 时间复杂度：O(n)，其中 n 是链表中的元素个数；
  • 空间复杂度：O(1)，因为只需要常数的空间。

    3. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val, next) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.next = (next===undefined ? null : next)
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @param {number} k
    11. * @return {ListNode}
    12. */
    13. var rotateRight = function(head, k) {
    14.   if(!head || !head.next){
    15.       return head
    16.   }
    17.   // 找到尾结点，将单链表形成环形链表
    18.   let tail = head
    19.   let length = 1
    20.   while(tail.next){
    21.       length++
    22.       tail = tail.next
    23.   }
    24.   tail.next = head
    25.   // 尾结点进行移动
    26.   k = k % length
    27.   for(let i = 0; i < length - k; i++){
    28.       tail = tail.next
    29.   }
    30.   // 找到头结点，断开环形链表
    31.   head = tail.next
    32.   tail.next = null
    33.   return head
    34. };

    4. 提交结果

    image.png