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.
Last updated
Was this helpful?