链表去重：有序与无序场景下的解决方案
链表作为一种常见的数据结构，在计算机科学中扮演着重要的角色。链表去重是链表操作中的一个基本问题，它涉及到如何有效地从链表中移除重复的元素。本文将围绕链表去重这一主题，分别针对有序链表和无序链表两种场景，探讨相应的解决方案。
链表去重的主要目的是确保链表中每个元素都是唯一的。在有序链表中，去重相对简单，因为重复的元素会相邻出现。而在无序链表中，去重则需要遍历整个链表，并使用额外的数据结构来记录已经出现过的元素。
有序链表去重
原理
有序链表去重的核心思想是：遍历链表，比较当前节点与其下一个节点，如果它们相同，则删除下一个节点；如果不同，则移动到下一个节点。
代码实现
python
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
def remove_duplicates_sorted(head):
current = head
while current and current.next:
if current.value == current.next.value:
current.next = current.next.next
else:
current = current.next
return head
测试代码
def print_list(head):
current = head
while current:
print(current.value, end=" ")
current = current.next
print()
创建有序链表
head = ListNode(1, ListNode(2, ListNode(2, ListNode(3, ListNode(4, ListNode(4, ListNode(5)))))))
去重
head = remove_duplicates_sorted(head)
打印去重后的链表
print_list(head)
分析
上述代码中，`remove_duplicates_sorted` 函数通过遍历链表，比较相邻节点值，实现了有序链表的去重。时间复杂度为 O(n)，空间复杂度为 O(1)。
无序链表去重
原理
无序链表去重需要遍历整个链表，并使用一个额外的数据结构（如集合）来记录已经出现过的元素。遍历过程中，如果发现当前元素已经在集合中，则将其删除。
代码实现
python
def remove_duplicates_unsorted(head):
seen = set()
current = head
while current:
if current.value in seen:
current = current.next
else:
seen.add(current.value)
current = current.next
return head
测试代码
创建无序链表
head = ListNode(3, ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(2, ListNode(1)))))))
去重
head = remove_duplicates_unsorted(head)
打印去重后的链表
print_list(head)
分析
上述代码中，`remove_duplicates_unsorted` 函数通过遍历链表，并使用集合 `seen` 来记录出现过的元素，实现了无序链表的去重。时间复杂度为 O(n)，空间复杂度为 O(n)。
总结
本文针对有序链表和无序链表两种场景，分别介绍了链表去重的解决方案。有序链表去重相对简单，只需遍历链表并比较相邻节点即可；而无序链表去重则需要遍历整个链表，并使用额外的数据结构来记录出现过的元素。两种方法的时间复杂度均为 O(n)，但空间复杂度不同，有序链表去重为 O(1)，而无序链表去重为 O(n)。
在实际应用中，应根据链表的特点和需求选择合适的去重方法。对于有序链表，去重操作简单高效；而对于无序链表，去重操作虽然复杂，但可以保证结果的唯一性。
Comments NOTHING