题目
给定一个链表,旋转链表,将链表每个节点向右移动 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
解题思路
快慢指针
/**
* Definition for singly-linked list.
* public class ListNode {
* public var val: Int
* public var next: ListNode?
* public init() { self.val = 0; self.next = nil; }
* public init(_ val: Int) { self.val = val; self.next = nil; }
* public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
* }
*/
class Solution {
func rotateRight(_ head: ListNode?, _ k: Int) -> ListNode? {
guard let head = head else { return nil }
var p1: ListNode? = head
var p2: ListNode? = head
var count = 1
var i = 0
var k = k
while i < k {
if let next = p2?.next {
count += 1
p2 = next
} else {
k = k % count
i = -1
p2 = head
}
i += 1
}
while p2?.next != nil {
p1 = p1?.next
p2 = p2?.next
}
if let next = p1?.next {
let tmp = next
p1?.next = nil
p2?.next = head
return tmp
} else {
return head
}
}
}
网友评论