LeetCode 61. 旋转链表(swift)

题目

给定一个链表，旋转链表，将链表每个节点向右移动 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
        }
    }
}