题目:
- 在O(1)的时间内删除链表节点
- 删除链表中重复的节点
题目1:在O(1)的时间内删除链表节点
给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间内删除该节点。举例说明
链表1->2->3,输入头结点head和待删除结点n2,输出删除之后的头结点,此时链表1->2。思路
常规思路
- 一般单向列表删除结点,就是从头遍历,找到这个结点之前的结点,指向这个结点之后的结点,就算是删除了这个结点。
- 这种方法的时间复杂度为O(n) 。
复制结点法
- 题目要求在O(1)时间内完成,所以应该避免遍历。
- 我们遍历的目的是为了找到这个结点前面的那个结点,所以我们可以 将待删除结点的下一个结点的值赋给待删除的结点,然后删除一个结点,就达到了删除结点的目的。
- 对于n-1个非尾节点,O(1)时间内可以删除,如果是尾节点则O(n),平均时间复杂度为[O(1)∗(n−1)+O(n)∗1]/n,时间复杂度还是O(1)。符合要求。不过该方法并没有判断需要删除的节点是否在链表中,为达到时间复杂度为O(1)的要求,将判断节点是否存在的责任推给了该方法的调用者。
注意边界条件的特殊处理
1)正常, 多个结点,删除的不是尾结点。
2)只有一个结点,删除尾结点(也是头结点)
3)有多个结点,删除尾结点代码
1 | public class _18_1 { |
输出
题目2:删除链表中重复的节点
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留,返回链表头指针。
举例说明
链表1->2->3->3->3->4->4>5,输入头结点head,输出删除之后的头结点,此时链表1->2>5。
思路
- 我们从头遍历整个链表。如果当前结点的值与下一个结点的值相同,那么它们就是重复的结点,都可以被删除。
- 为了保证删除之后的链表仍然是相连的而没有中间断开,我们要把当前的前一个结点和后面值比当前结点的值要大的结点相连。我们要确保prev要始终与下一个没有重复的结点连接在一起。
- 头结点可能与后面的结点重复,也就是说头结点也可能被删除,所以在链表头添加一个结点。
代码
1 | public class _18_2 { |