# [資演] 5-Linked List (II): Singly linked list 上的操作
###### tags: `資演`

## Linked list 的插入操作
對於一個非空的 linked list，我們的插入(insertion)可以有三種可能：
1. 在 head 之前插入，所插入節點成為新的 head
2. 在中間插入，插入的節點成為中間的節點
3. 在 tail 之後插入，所插入節點成為新的 tail

於是，插入操作的演算法流程如下：

一個定義在`LinkedList`裡面的`insert`方法的程式碼如下：：

def insert(self, value, location):
    newNode = Node(value)
    if self.head is None:
        self.head = newNode
        self.tail = newNode
    else:
        if location == 0:
            newNode.next = self.head
            self.head = newNode
        elif location == -1:
            newNode.next = None
            self.tail.next = newNode
            self.tail = 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

## 巡訪 linked list
Linked list的巡訪相當簡單，只要順著指標一個一個連下去就好了：

其程式碼如下：

def traverse(self):
    if self.head is None:
        return "The linked list does not exist"
    else:
        node = self.head
        while node is not None:
            print(node.value)
            node = node.next

## 在 linked list 裡面尋找一個元素
尋找一個元素的操作和巡訪相當類似，主要有以下兩點和巡訪不同：
1. 我們需要先輸入一個要尋找的目標值
2. 終止條件為找到那個值


def search(self, nodeValue):
    if self.head is None:
        return "The linked list does not exist"
    else:
        node = self.head
        while node is not None:
            if node.value == nodeValue:
                return node.value
            node = node.next
        return "The node does not exist in this linked list"

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



def delete(self, location):
    if not self.head:
        return "The linked list does not exist"
    else:
        if location == 0:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:
                self.head = self.head.next
        elif location == -1:
            if self.head == self.tail:
                self.head = None
                self.tail = None
            else:
                node = self.head
                while node:
                    if node.next == self.tail:
                        break
                    node = node.next
                node.next = None
                self.tail = node  
        else:
            tmp = self.head
            index = 0
            while index < location-1:
                tmp = tmp.next
                index += 1
            nextNode = tmp.next
            tmp.next = nextNode.next    

## 例題
* 找出位在 linked list 最中間的那個數
這是一個經典的題目，想想看在只能單向尋訪整個linked list、而且不能由index來呼叫的時候，你要怎麼找出最中間的那個節點呢？
:::spoiler 解答
想像現在有一隻烏龜和一隻兔子在賽跑。兔子跑步的速度是一直維持在烏龜的速度的兩倍，當兔子跑到終點的時候，烏龜在哪裡？
答案是在中點。
運用這個概念，我們可以使用兩個指針來尋訪整個linked list，一個快指針一次跳兩格(`fast`)，一個慢指針一次只跳一格(`slow`)。當快指針走到linked list的末端的時候，慢指針應該就會在我們希望得到的中間點上。

    class Solution:
        def middleNode(self, head):
            fast = head
            slow = head        
            try:
                while fast:
                    fast = fast.next.next
                    slow = slow.next
            except:
                return slow

            return slow

:::

* 相加兩個整數
現在你手上有兩個非空的 linked list，他們分別代表兩個大於等於 0 的整數。每個 linked list 上的節點儲存一個位數，儲存順序和你閱讀那個整數的順序相反，例如
代表的是 $342+465=807$。
:::spoiler 解答
因為linked list上的數字順序已經是由低位數到高位數排列，你可以使用你平常心算加法時的邏輯來編寫這個程式。

    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    
    class Solution:
        def addTwoNumbers(self, l1, l2):
            offset = 0
            this1 = l1
            this2 = l2
            this_head = ListNode()
            this = this_head
            while this1 or this2 or int(offset) > 0:            
                val1 = this1.val if this1 else 0
                val2 = this2.val if this2 else 0
                this.val = (val1 + val2 + offset) % 10
                offset = int((val1 + val2 + offset )/ 10)
                this1 = this1.next if (this1 and this1.next) else None
                this2 = this2.next if (this2 and this2.next) else None


                if offset == 0 and not (this1 or this2):
                    break
                else:
                    nnode = ListNode()
                    this.next = nnode
                    this = this.next

            return this_head

:::

* 去除重複的數字
給定一個已經由小到大排列的 linked list，去除裡面重複出現的元素，只留下一個。也就是說，最後的結果會是一個由小到大排列且每個元素都不相同的 linked list。

:::spoiler 解答
這題可以算是delete方法的應用：刪除linked list中不特定的元素。

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution(object):
        def deleteDuplicates(self, head):
            """
            :type head: ListNode
            :rtype: ListNode
            """
            x = head

            if x == None:
                return None
            while (x.next != None):
                if (x.next.val == x.val):
                    x.next = x.next.next
                else:
                    x = x.next
            return head

:::