LeetCode 61. 旋转链表(swift)

作者: freesan44 | 来源:发表于2023-06-15 07:42 被阅读0次

    题目

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

    相关文章

      网友评论

        本文标题:LeetCode 61. 旋转链表(swift)

        本文链接:https://www.haomeiwen.com/subject/lzakydtx.html