题目一
题目一
- 审题：带头结点，使元素递增有序
- 解题思路:链表的直接排序容易出错且比较麻烦,在题目不对空间复杂度作要求的情况下，可以将链表元素放入数组中,对数组进行排序再放回链表中.
实现
void sortLinkList(linkList *p){
Node* a = new Node[10];
int i = 0;
Node * node = p->next;
while(node){
a[i++]=node;
}
for(int j = 0;j<=i;j++){
for(int k = 0;k<=i-1;k++){
if(a[j]->data<a[k+1]->data){
Node * temp = a[j];
a[j] = a[k];
a[k]=temp;
}
}
}
for(int l = 0;l<=i;l++){
p->next = a[l];
p = p->next;
}
}
题目二
题目二
- 审题：带头结点,无序,
- 解题思路:跟踪前驱节点,逐个检查
实现
void deleteInRange(int left,int right,linkList * p){
Node * node = p->next;
Node * pre = p;
while(p){
if(left<p->data&&p->data<right){
pre -> next = p->next;
delete(p)
p = pre->next;
}
else{
pre = p;
p= p->next;
}
}
}
题目三
题目三
- 审题：带头结点,无序,
- 解题思路:跟踪前驱节点,逐个检查
实现
void deleteInRange(int left,int right,linkList * p){
Node * node = p->next;
Node * pre = p;
while(p){
if(left<p->data&&p->data<right){
pre -> next = p->next;
delete(p)
p = pre->next;
}
else{
pre = p;
p= p->next;
}
}
}
