---
# System prepended metadata

title: secure linked list

---

# secure linked list
> 實作一個 linked list，但是每個 node 都有一個 `hash_value = hash(self.value, self.next.hash_value)`，node 的 value 是 string，實作他的函數 `add_node(string)` ，每次加一個 node 到 list 的前面。
> 
- **Discussion**
    - 資料結構可能類似
    
    ```python
    class SecureListNode():
    	.value
    	.hash_value
    	.next
    ```
    
    - 覺得就是實作題，但還是有發生一些小 bug（邊界條件沒檢查乾淨），面試官強調要儘量檢查沒有 bug 再與他確定解法。
    
    H -> a
    H -> b -> a
    H -> c -> b -> a
```python=
class Node:
    def __init__(self, val, preHash):
        self.val = val
        self.hash_value = self.hashfunc(self.value, preHash)
        self.next = None
    def hashfunc(self, a, b):
        return a + b


class LinkedList():
    def __init__(self):
        self.head = None
        self.tail = None
        
    def Insert(self, val):
        if self.head is None:
            newNode = Node(val, "")
            self.head = newNode
            self.tail = newNode
        else:
            newNode = Node(val, self.head.hash_value)
            newNode.next = self.head
            self.head = newNode
H -> c -> b -> a  secure
H -> d -> f -> g 
H -> g

def coversion(root):
    if not root:
        return None
    
    newRoot = Node(root.val, "")
    curNew = newRoot
    
    pre = root
    cur = root.next
    while cur:
        curNew.next = Node(root.val, pre.hash_val)
        curNew = curNew.next
        
        pre = cur
        cur = cur.next
        
    return newRoot

```