已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点

题目意思：已知非空性链表由list指出，链结点的构造为（data, link）。请写一个算法，将链表中数据域值最小的那个链结点移动到链表的最前面。要求：不得额外申请新的链结点。

解析：

1.首先找到链表中数据域值最小的那个结点；

2.将该结点从当前位置删除，并插入到链表的最前面。

实现代码：

def move_min_head(list):
if len(list)<2: return list

i=0
j=i+1
min_value=list[i][0]
min_index=i

while j<len(list):
if list[j][0]<min_value:
min_value=list[j][0]
min_index=j

j+=1

if min_index==0: return list
else:
del list[min_index]
list.insert(0,[min_value,None])
return list

注意事项：在执行删除和插入操作时，必须保证操作的复杂度为O(1)。在Python中，del和insert操作都可以满足这个要求。

相关问题

已知非空线性链表由list指出，链结点的构造为（data,link）。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。

算法如下：

1. 定义一个指针minNode，指向链表的第一个结点，用于记录当前最小值的结点。
2. 定义一个指针preMinNode，指向minNode的前一个结点，用于记录当前最小值结点的前一个结点。
3. 从链表的第二个结点开始遍历链表，比较每个结点的data域值与minNode的data域值的大小，如果小于minNode的data域值，则将minNode指向该结点，preMinNode指向minNode的前一个结点。
4. 如果minNode不是链表的第一个结点，则将preMinNode的link指向minNode的link，将minNode插入到链表的最前面，即将minNode的link指向链表的第一个结点，将list指向minNode。
5. 返回链表list。

代码如下：

Node* moveMinNodeToFront(Node* list) {
    if (list == NULL || list->link == NULL) {
        return list;
    }
    Node* minNode = list;
    Node* preMinNode = NULL;
    Node* p = list->link;
    while (p != NULL) {
        if (p->data < minNode->data) {
            minNode = p;
            preMinNode = list;
        } else {
            preMinNode = p;
        }
        p = p->link;
    }
    if (minNode != list) {
        preMinNode->link = minNode->link;
        minNode->link = list;
        list = minNode;
    }
    return list;
}

已知非空线性链表l的链结点按结点数据域值非递减链接，请写一算法，删除链表中数据域值相同的多余链结点。

### 回答1：
算法如下：

1. 定义指针p和q，分别指向链表的第一个结点和第二个结点。

2. 循环遍历链表，直到q指向链表的最后一个结点。

3. 如果p结点的数据域值等于q结点的数据域值，则删除q结点，并将q指向下一个结点。

4. 如果p结点的数据域值不等于q结点的数据域值，则将p指向q，q指向下一个结点。

5. 返回链表的头结点。

代码实现如下：

struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode *p = head, *q = head->next;
while (q != NULL) {
if (p->val == q->val) {
p->next = q->next;
free(q);
q = p->next;
} else {
p = q;
q = q->next;
}
}
return head;
}

### 回答2：
这道题的主要思路就是遍历整个链表，如果出现相同的数据域，就删除后面的那个结点。由于链表中的结点按数据域非递减链接，所以我们只需要比较当前结点与下一个结点的数据域是否相等即可。

具体的算法步骤如下：

1. 首先判断链表是否为空，如果为空则直接返回。

2. 定义两个指针p和q分别指向链表的头结点和第二个结点。

3. 遍历整个链表，如果当前结点的数据域与下一个结点的数据域相等，则删除下一个结点，将p指向第一个相同数据域的结点，q指向p的下一个结点；如果当前结点的数据域与下一个结点的数据域不相等，则将p和q各后移一个结点。

4. 最后返回链表的头结点。

下面是具体的代码实现：

void delete_repeat_nodes(ListNode *head)
{
if (head == nullptr || head->next == nullptr) {
return;
}

ListNode *p = head; // 指向第一个不重复的结点
ListNode *q = head->next; // 指向p的下一个结点

while (q != nullptr) {
if (p->val == q->val) {
p->next = q->next; // 删除q结点
delete q;
q = p->next; // 继续判断后面的结点
} else {
p = p->next;
q = q->next;
}
}
}

这个算法的时间复杂度为O(n)，其中n为链表的长度，因为需要遍历整个链表一次。空间复杂度为O(1)，因为只需要定义几个指针变量用来遍历链表，不需要额外的存储空间。

### 回答3：
要删除链表中数据域值相同的多余链结点，我们可以使用双指针来遍历链表，同时使用一个哈希表来记录已经出现过的数据值。

具体来说，我们可以定义一个指针p和一个指针q，初始时它们都指向链表头结点。然后我们在哈希表中记录下第一个结点的数据域值，即head->val。接着，我们让q指针向后移动一个结点，判断它的数据域值是否出现过。

如果q指向的结点的数据域值出现过，那么我们就将此结点删除，即将p指针的next指向q的下一个结点，并释放q结点的内存空间。否则，我们就在哈希表中记录下q结点的数据域值，并将p指针和q指针同时向后移动一个结点。

当q指针遍历完整个链表之后，我们就可以得到一个没有多余链结点的链表了。

具体算法实现如下：

1. 初始化哈希表和双指针p和q，让它们都指向头结点。

2. 在哈希表中记录下头结点的数据域值。

3. 如果q指针不为NULL，则继续遍历链表。

4. 如果q指向的结点的数据域值出现过，则将此结点删除；否则，在哈希表中记录下q结点的数据域值。

5. 将p指针和q指针同时向后移动一个结点，继续遍历链表。

6. 返回新的链表头结点。

代码实现如下：

struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) return NULL;

struct ListNode* p = head; // p指针指向当前节点的前一个节点
struct ListNode* q = head->next; // q指针指向当前节点

unordered_map<int, bool> hash; // 哈希表存储已经出现过的值
hash[head->val] = true;

while (q) {
if (hash[q->val]) {
p->next = q->next;
free(q);
} else {
hash[q->val] = true;
p = q;
}
q = p->next;
}

return head;
}

这个算法的时间复杂度是O(N)，其中N是链表中的结点数。空间复杂度也是O(N)，因为我们需要使用一个哈希表来记录已经出现过的数据值。