删除带头节点单链表l中重复的节点
时间: 2024-10-15 07:26:46 浏览: 35
删除带头节点单链表`l`中重复的节点,通常可以采用迭代的方式来实现。基本思路是维护两个指针,一个指向当前节点,另一个叫做“暂存”指针,每次移动一步。如果当前节点的值等于暂存节点的值,则将当前节点从链表中移除;否则,将当前节点更新为其下一个节点,并将暂存指针更新为当前节点。
以下是步骤描述:
1. 初始化暂存指针`temp`和当前指针`current`都设置为头结点`head`。
2. 循环遍历链表,直到`current`为空:
- 如果`current->data`(当前节点的值)与`temp->data`相同,说明存在重复,将`current`的next指向前一个节点,即`current->next = temp->next`。
- 否则,将`temp`移动到`current`的位置,即`temp = current`,然后`current`移到下一个节点,即`current = current->next`。
3. 当循环结束,链表中重复节点已去除,`temp`指向的就是新链表的最后一个节点,所以返回`temp`作为新的头节点。
```python
def deleteDuplicates(head):
if not head or not head.next:
return head
dummy = ListNode(0) # 创建哑节点,避免处理空链表的情况
dummy.next = head
current = head
while current and current.next:
if current.data == current.next.data:
next_node = current.next.next
current.next = None
current = next_node
else:
current = current.next
return dummy.next
```
阅读全文