题目描述
一个单链表中有 m 个结点,每个结点上的元素的绝对值不超过 n。
现在,对于链表中元素的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。
请输出筛选后的新链表。
例如,单链表 21 -> -15 -> -15 -> -7 -> 15
,在进行筛选和删除后,变为21 -> -15 -> -7
。
输入样例:
21->-15->-15->-7->15
输出样例:
21->-15->-7
数据范围
1≤m≤1000,
1≤n≤10000
思路:
这道题我是采用的空间换时间。
1. 使用辅助数组记录链表中已经出现过的值,从而只对链表进行一次扫描
2. 因为结点的值的绝对值<=n,所以申请n+1(0~n)个空间的辅助数组即可
3. 结点的值表示数组的下标,对应的位置的值取0或1,0表示该结点的值未出现过,1则代表出现过
4. 如果数组的值==0,保留该结点,反之删除该结点
C 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* Note: The returned array must be malloced, assume caller calls free().
*/
typedef struct ListNode LNode;
struct ListNode* filterList(struct ListNode* head) {
//本题整体上我采用的是空间换时间
LNode *tempHead = (LNode *)malloc(sizeof(LNode));//创建一个虚拟头结点方便操作
tempHead->next = head;
int *arr = (int *)malloc(sizeof(int) * 10001);
for(int i = 0; i < 10001; i++)//初始化数组
arr[i] = 0;
while(tempHead->next){
int data = abs(tempHead->next->val);//将结点元素的绝对值保存到data中
if(arr[data] == 0){//表示该结点的val没有出现过
arr[data] = 1;//设置为出现过
tempHead = tempHead->next;
}else{
LNode *temp = tempHead->next;
tempHead->next = temp->next;
free(temp);
}
}
free(arr);
return head;
}