面试题 02.01. 移除重复节点
编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入:[1, 2, 3, 3, 2, 1] 输出:[1, 2, 3]
示例2:
输入:[1, 1, 1, 1, 2] 输出:[1, 2]
提示:
- 链表长度在[0, 20000]范围内。
- 链表元素在[0, 20000]范围内。
进阶:
如果不得使用临时缓冲区,该怎么解决?
解题思路:利用三指针思路遍历数组,两个指针找到重复节点删除,利用第三个指针链接删除之后的链表,保证链表结构。
总结这道题需要非常缜密的心思!大家需要多多,有着非常多的东西需要思考!
代码实现:
struct ListNode* removeDuplicateNodes(struct ListNode* head){if(head == NULL || head->next == NULL){return head;}struct ListNode* prev = NULL;struct ListNode* Cur = head;struct ListNode* Next = head->next;while (Next){if(Cur->data != Next->data){prev = Cur;Cur = Next;Next = Next->next;}else{while (Next && Cur->data == Next->data){Next = Next->next;//头节点就是重复节点if(prev){prev->next = Next;}else{head = Next;}}while (Cur != Next){ListNode* del = Cur;Cur =Cur->nextfree(del);}if(Next) //Next不为空指针Next = Next->next; }} return head;
}
谢谢大家的点赞和收藏!!👍