过两个指针(pa和pb)比较两个链表的节点,选取较小值加入新链表,直到某一个链表遍历结束为止。代码实现了去重的功能,当遇到相同值时,只选择一次。最终返回新链表的头节点。
时间: 2024-09-27 22:06:09 浏览: 19
这个问题描述的是经典的双指针算法,在链表领域常常用于实现去重功能。通常会创建一个新的链表来保存处理结果,其中`pa`和`pb`分别指向原链表的两个节点。这两个指针同时开始遍历,如果当前`pa`和`pb`节点的值相等,并且`pa`已经访问过(可以通过一个额外的哈希集合或者标志位跟踪),那么就跳过`pb`继续;如果不相等,或者`pb`还没访问过,就把`pb`的值添加到新链表并移动指针。这个过程持续到其中一个链表遍历完。
以下是一个简单的Python代码示例:
```python
def removeDuplicates(head):
if not head or not head.next:
return head
dummy = ListNode(0)
dummy.next = head
pa = pb = dummy
hash_set = set()
while pa and pb:
if pb.val in hash_set:
pb = pb.next
else:
hash_set.add(pb.val)
pa.next = pb
pa = pa.next
pb = pb.next
# 如果pb未遍历完,则将剩余部分连接到新链表
while pb:
hash_set.add(pb.val)
pb = pb.next
pa.next = pb
pa = pa.next
return dummy.next
```
在这个函数中,`ListNode`是链表节点的结构,`hash_set`用于存储已访问过的节点值。最后返回的新链表头节点就是`dummy.next`。
阅读全文