本文共 1214 字,大约阅读时间需要 4 分钟。
题目:
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点保留一个,返回链表头指针。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->3->4->5
代码1:时间复杂度O(n),空间复杂度O(n)
ListNode* remove(ListNode* head){ if (head == nullptr || head->next == nullptr) return head; unordered_set s; s.insert(head->val); ListNode* pre = head; ListNode* cur = head->next; while (cur != nullptr) { if (s.count(cur->val)) { pre->next = cur->next; cur = cur->next; } else { s.insert(cur->val); pre = pre->next; cur = cur->next; } } return head;}
代码2:时间复杂度O(n^2),空间复杂度O(1)
ListNode* remove(ListNode* head){ if (head == nullptr || head->next == nullptr) return head; ListNode* cur = head; while (cur != nullptr) { ListNode* pre = cur; ListNode* next = cur->next; while (next != nullptr) { if (cur->val == next->val) { next = next->next; pre->next = next; } else { pre = next; next = next->next; } } cur = cur->next; } return head;}
参考资料:
左程云著《程序员代码面试指南》
转载地址:http://ktwab.baihongyu.com/