# [資演] 6- Linked List (III): Circular Linked List 上的操作
###### tags: `資演`
## 創建一個 circular linked list
前面已經說過，circular linked list 只是把 singly linked list 的 tail 連到 head 上。我們首先創建一個只有一個節點的circular linked list：

和前面的singly linked list類似地，首先我們建立一個`CircularLinkedList`物件，這個物件含有兩個屬性，`head`和`tail`。

接著，我們建立一個節點，並將這個節點插入到前面建立的`CircularLinkedList`物件中，也就是將`head`和`tail`都設定為這個節點。因為現在創建的是circular linked list，所以這個節點的next必須指到自己。

具體流程如下：

注意到在建立物件之前，我們必須要先有相應的類別(class)，才能創建那個類別的實例(instance)。建立類別的程式碼也和singly linked list類似：

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

如此我們便可以在CircularLinkedList類別實作create方法：

class CircularLinkedList:
    ...
    
    def create(self, nodeValue):
        node = Node(nodeValue)
        node.next = node
        self.head = node
        self.tail = node

## Circular linked list 的插入操作
和singly linked list的狀況類似，對於一個非空的circular linked list，我們想插入一個節點，同樣可以分為以下三種情形：
1. 在 head 之前插入，所插入節點成為新的 head
2. 在中間插入，插入的節點成為中間的節點
3. 在 tail 之後插入，所插入節點成為新的 tail

注意對於circular linked list並沒有真正的頭或尾，在這邊給定兩個屬性`head`和`tail`只是為了方便起見。有些實作只會使用`head`或`tail`的其中一個。

circular linked list上的插入和singly linked list類似，差別只在於要注意circular linked list的的`tail`必須接到`head`上，也就是，`tail`的`next`必須是`head`。

由以上邏輯我們可以畫出插入操作的流程圖：

其程式碼如下：

class CircularLinkedList:
    ...
    
    def insert(self, nodeValue, location):
        if self.head is None:
            return "The head reference is None"
        else:
            newNode = Node(value)
            if location == 0:
                newNode.next = self.head
                self.head = newNode
                self.tail.next = newNode
            else:
                tempNode = self.head
                index = 0
                while index < location - 1:
                    tempNode = tempNode.next
                    index += 1
                nextNode = tempNode.next
                tempNode.next = newNode
                newNode.next = nextNode

## 巡訪 circular linked list
Circular linked list 的巡訪和singly linked list的完全相同，故在此不再重複介紹。

## 在 circular linked list 裡面尋找一個元素
Circular linked list 的search和singly linked list的完全相同，故在此亦不再重複介紹。

## Circular linked list 的刪除操作
對於 circular linked list 的刪除操作，我們一樣可以分為三種情形來看：
1. 刪除第一個節點，即head
2. 刪除中間節點
3. 刪除最後一個節點，即tail

我們同樣可以採用和singly linked list類似的思路，只是要注意circular linked list的的`tail`必須接到`head`上。


其程式碼實作如下：

class CircularLinkedList:
    ...
    
    def delete(self, location):
        if self.head is None:
            print("The list is empty.")
        else:
            if location == 0:
                if self.head == self.tail:
                    self.head.next = None
                    self.head = None
                    self.tail = None
                else:
                    self.head = self.head.next
                    self.tail.next = self.head
            else:
                tempNode = self.head
                index = 0
                while index < location - 1:
                    tempNode = tempNode.next
                    index += 1
                nextNode = tempNode.next
                tempNode.next = nextNode.next

## 例題
* [探測Linked List裡面有沒有cycle](https://leetcode.com/problems/linked-list-cycle/)
給定一個linked list，我們想寫一個函式，探測這個linked list有沒有cycle(循環)在裡面。如果有cycle，回傳`True`，否則回傳`False`。
::: spoiler 提示
使用Floyd's Cycle Finding Algorithm：想像有兩個跑者在跑道上用不同的速度跑步，如果跑道是一個圈圈，會發生什麼事？
:::

::: spoiler 解答
當兩個跑者在跑道上用不同的速度跑步時，如果跑道是一個圈圈，那麼跑得快的人最後會從後面追上跑得慢的人（但比他多跑了一圈）。所以我們只要寫一個程式讓兩個指針去賽跑，如果兩個指針在某個時間點重合了，那就代表這個跑道上有圈圈；否則，就代表跑道上沒有圈圈。

    class Solution:
        def hasCycle(self, head: ListNode) -> bool:
            if head is None:
                return False
            slow = head
            fast = head.next
            while slow != fast:
                if fast is None or fast.next is None:
                    return False
                slow = slow.next
                fast = fast.next.next
            return True
    :::
* [插入一個已排序好的circular linked list](https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/)
    給定一個已經由小到大排序好的circular linked list的head，我們想要寫一個函式，這個函式可以把一個新的值`insertVal`插入這個已經排序好的circular linked list裡面，並且讓它保持為一個排序好的circular linked list。如果給定的是一個空的list，則創建一個新的circular linked list，並回傳那個插入的節點。
    注意到在這邊我們回傳的節點可以是這個circular linked list上的任何一個節點，因為對於circular linked list並沒有真正意義上的`head`。
![](https://hackmd.io/_uploads/B1e3HXgCK.png)
![](https://hackmd.io/_uploads/B1onSmxCF.png)

    ::: spoiler 解答
    這題我們一樣可以使用兩個跑者，`curr`和`prev`，但這次他們的速度是一樣的，只是`curr`比`prev`快一格。這樣當我們找到適合的位置插入時，就可以直接插入這兩個節點的中間。

class Solution:
def insert(self, head: 'Node', insertVal: int) -> 'Node':
node = Node(insertVal)

if not head:
node.next = node
return node

prev, curr = head, head.next

while prev.next != head:
if prev.val <= node.val <= curr.val:
break

if prev.val > curr.val and (node.val > prev.val or node.val < curr.val):
break

prev, curr = prev.next, curr.next

# Insert node
node.next = curr
prev.next = node

return head
:::