# 对链表进行插入排序

<p>对链表进行插入排序。</p>

<p><img alt="" src="https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif"><br>
<small>插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。<br>
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。</small></p>

<p>&nbsp;</p>

<p><strong>插入排序算法：</strong></p>

<ol>
	<li>插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。</li>
	<li>每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。</li>
	<li>重复直到所有输入数据插入完为止。</li>
</ol>

<p>&nbsp;</p>

<p><strong>示例 1：</strong></p>

<pre><strong>输入:</strong> 4-&gt;2-&gt;1-&gt;3
<strong>输出:</strong> 1-&gt;2-&gt;3-&gt;4
</pre>

<p><strong>示例&nbsp;2：</strong></p>

<pre><strong>输入:</strong> -1-&gt;5-&gt;3-&gt;4-&gt;0
<strong>输出:</strong> -1-&gt;0-&gt;3-&gt;4-&gt;5
</pre>


## template

```python

class LRUCache:
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.maxlength = capacity
        self.array = {}
        self.array_list = []

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        value = self.array.get(key)

        if value is not None and self.array_list[0] is not key:
            index = self.array_list.index(key)
            self.array_list.pop(index)
            self.array_list.insert(0, key)

        value = value if value is not None else -1
        return value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """

        if self.array.get(key) is not None:
            index = self.array_list.index(key)
            self.array.pop(key)
            self.array_list.pop(index)

        if len(self.array_list) >= self.maxlength:
            key_t = self.array_list.pop(self.maxlength - 1)
            self.array.pop(key_t)

        self.array[key] = value
        self.array_list.insert(0, key)


```

## 答案

```python

```

## 选项

### A

```python

```

### B

```python

```

### C

```python

```