Collections.rotate()实现原理
List元素移位可以看做是两个子列表进行交换
左移两位: [8, 5, 3, 6, 2] -> [3, 6, 2, 8, 5]
就是将[8,5]跟[3,6,2]交换位置
右移两位: [8, 5, 3, 6, 2] -> [6, 2, 8, 5, 3]
就是将[6,2]跟[8,5,3]交换位置
根据列表长度size和移位个数distance,可以计算出两个子列表的分隔点,有了两个子列表后,两个子列表的顺序交换可以通过三次翻转实现。
比如,有A和B两个子列表,A有m个元素,B有n个元素:a1a2…amb1b2…bn,要变为b1b2…bna1a2…am,可经过三次翻转实现:
(1)翻转子列表Aa1a2…amb1b2…bn→ am…a2a1b1b2…bn
(2)翻转子列表Bam…a2a1b1b2…bn→ am…a2a1bn…b2b1
(3)翻转整个列表am…a2a1bn…b2b1→ b1b2…bna1a2…am这个算法的整体实现代码为:
