Algorithm：61. Rotate List
https://leetcode-cn.com/problems/rotate-list/
Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example 1:
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
Example 2:
Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
分析：連結清單問題一般有兩種思路，一是先求對外連結表長度，然後利用長度計算下标，類似于數組操作；另一種是用雙指針，可以是快慢指針，也可以是滑動視窗，其思想是把下标關系轉換成兩個指針之間的距離，然後同時前進。
下面也用這兩種思路來解答這一題。有點特别的是，當k大于數組長度時，雙指針解法仍然要計算數組長度，否則，會很低效。
這兩種解法時間複雜度都是O(n)，空間複雜度都是O(1)。當k小于等于連結清單長度時，解法二應該是優于解法一的，因為隻需要周遊一遍；當k大于連結清單長度時，兩種解法是差不多的，甚至解法一可能更快一點，因為解法二中多了一個指針需要移動。從Leetcode的送出記錄來看，解法一更快一點，且解法一思路更清晰一些，是以個人傾向于解法一。當然了，解法二也可以像解法一一樣，先求對外連結表長度，然後取模，然後再利用雙指針移動，但感覺有點多次一舉了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
// 解法二：雙指針。當k小于等于連結清單長度時，周遊一遍搞定；當k大于連結清單長度時，第一次周遊仍然要計算對外連結表長度然後将k取模運算，否則當k遠遠大于連結清單長度時，快指針會做很多次無效移動。
public ListNode rotateRight(ListNode head, int k) {
if(head == null || head.next == null || k == 0)
return head;
ListNode p = head;
ListNode q = head;
int i;
for(i=1; i<= k && p.next != null; i++, p=p.next);
if(i <= k) { // i+1 is length of list
k %= i;
p = head;
for(i=0; i<k; i++, p=p.next);
}
if(p == q)
return head;
while(p.next != null) {
p = p.next;
q = q.next;
}
ListNode temp = q.next;
q.next = null;
p.next = head;
head = temp;
return head;
}
// 解法一：先求出長度，再計算需要斷開的位置，将後半段插到前面去，傳回新的連結清單頭
private ListNode solutaion_1(ListNode head, int k) {
if(head == null || k == 0)
return head;
ListNode p = head;
int size = 1;
while(p.next != null) {
p = p.next;
size++;
}
// now p is point to the end
k %= size;
if(k == 0)
return head;
ListNode q = head;
for(int i=1; i< size-k; i++, q=q.next);
// now q is point to the k+1 from the end
ListNode temp = q.next;
q.next = null;
p.next = head;
head = temp;
return head;
}
}
Review: Cloud Computing History
https://medium.com/pgs-software/cloud-computing-history-7c2c188a30a
文章介紹了雲計算的曆史和演進過程，主要分為如下幾塊内容：
- 時間共享主機。在19世紀50年代到80年代期間，計算機很昂貴，多個使用者共用一台計算機很普遍，那時主要是通過時間片輪轉的方式共享，類似于現在單核cpu對多線程的排程。https://en.wikipedia.org/wiki/Time-sharing
- 網際網路。19世紀50年代末出現區域網路，直到90年代，Internet才誕生。網際網路的誕生催生了大量的網絡應用，也激發了對伺服器和資料中心的大量需求。
- 虛拟機。虛拟機的概念其實很早就出現了，1966年IBM就在作業系統中引入了虛拟機。2013年誕生的docker，是一種作業系統級别的虛拟化産品，它的出現使得微服務架構蓬勃發展。
- SaaS, PaaS, IaaS
- 真正的雲。亞馬遜EC2、微軟Azure Virtual Machines、谷歌Google Compute Engine
- 超越。
- 商業視角。Businesses that are able to keep up with these changes stand to continually gain the most benefits compared to those who sit idly by.與無所事事的人相比，能夠跟上變化的企業将持續獲得最大收益。
Tip:使用MySQL的官方Docker鏡像如何初始化資料庫
我使用的是官方mariadb基礎鏡像
mariadb:latest
，我們隻要把初始化資料庫的sql檔案放到
/docker-entrypoint-initdb.d/
目錄下，容器在啟動的時候就會執行這個sql。除了sql檔案，同樣也支援sh腳本和sql.gz檔案。
有一點需要注意，這個初始化工作隻會執行一次，一旦資料庫中已經有資料了，就不會再次初始化。
上述初始化工作是在基礎鏡像的
docker-entrypoint.sh
腳本裡做的，這裡面會判斷在mysql的資料目錄下是否有
/mysql
子目錄，如果有的話，就不執行初始化的邏輯：
...
DATADIR="$(_get_config 'datadir' "[email protected]")"
if [ ! -d "$DATADIR/mysql" ]; then
...
for f in /docker-entrypoint-initdb.d/*; do
case "$f" in
*.sh) echo "$0: running $f"; . "$f" ;;
*.sql) echo "$0: running $f"; "${mysql[@]}" < "$f"; echo ;;
*.sql.gz) echo "$0: running $f"; gunzip -c "$f" | "${mysql[@]}"; echo ;;
*) echo "$0: ignoring $f" ;;
esac
echo
done
![ARTS Week 25ARTS Week 25[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)