50217. Sorted Doubly Linked List
難度：3.5/5
AC率很低但意外地寫很順。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82#include <stdio.h>
#include <stdlib.h>
#include "function.h"
// typedef struct listnode {
// int data;
// struct listnode *next;
// struct listnode *prev;
// } ListNode;
//
// typedef struct linkedlist{
// struct listnode *head;
// struct listnode *tail;
// } LinkedList;
void insert(LinkedList *list, int data){
ListNode* new_node = (ListNode*) malloc(sizeof(ListNode));
new_node->data = data;
if(list->head == NULL){
new_node->next = NULL;
new_node->prev = NULL;
list->head = new_node;
list->tail = new_node;
}
else{
if(data <= list->head->data){
new_node->next = list->head;
new_node->prev = NULL;
list->head->prev = new_node;
list->head = new_node;
}
else if(data >= list->tail->data){
new_node->next = NULL;
new_node->prev = list->tail;
list->tail->next = new_node;
list->tail = new_node;
}
else{
ListNode *l, *r = list->head;
while(data >= r->data) r = r->next;
l = r->prev;
new_node->next = r;
new_node->prev = l;
r->prev = new_node;
l->next = new_node;
}
}
}
void delete_head(LinkedList *list){
if(list->head == NULL) return;
if(list->head == list->tail){
free(list->head);
list->head = NULL;
list->tail = NULL;
}
else{
ListNode* h = list->head;
list->head = list->head->next;
list->head->prev = NULL;
free(h);
}
}
void delete_tail(LinkedList *list){
if(list->tail == NULL) return;
if(list->head == list->tail){
free(list->head);
list->head = NULL;
list->tail = NULL;
}
else{
ListNode* t = list->tail;
list->tail = list->tail->prev;
list->tail->next = NULL;
free(t);
}
}