137 - 61 旋转链表

题目

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

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL

解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL

示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL

解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

解答

先变成一个环，然后旋转。。

var rotateRight = function(head, k) {
  if (!head || !head.next || !k) {
    return head
  }
  let len = 1
  headNew = head
  while (head.next) {
    head = head.next
    len++
  }
  head.next = headNew
  k = len - k % len - 1
  while (k) {
    headNew = headNew.next
    k--
  }
  const ans = headNew.next
  headNew.next = null
  return ans
};

Runtime: 64 ms, faster than 71.56% of JavaScript online submissions for Rotate List.

Memory Usage: 35.6 MB, less than 100.00% of JavaScript online submissions for Rotate List.

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or k == 0:
            return head
        _len = 1
        headNew = head
        while head.next:
            head = head.next
            _len += 1
        head.next = headNew
        k = _len-k % _len-1
        while k:
            headNew = headNew.next
            k -= 1
        ans = headNew.next
        headNew.next = None
        return ans

Runtime: 32 ms, faster than 99.50% of Python3 online submissions for Rotate List.

Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for Rotate List.

func rotateRight(head *ListNode, k int) *ListNode {
    if head == nil || head.Next == nil || k == 0 {
        return head
    }
    _len := 1
    headNew := head
    for head.Next != nil {
        head = head.Next
        _len++
    }
    head.Next = headNew
    k = _len - k%_len - 1
    for k != 0 {
        headNew = headNew.Next
        k--
    }
    ans := headNew.Next
    headNew.Next = nil
    return ans
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Rotate List.

Memory Usage: 2.5 MB, less than 75.00% of Go online submissions for Rotate List.