题目一：在O(1)时间内删除链表的节点，给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。
解题思路：
不同于顺序查找删除的节点，本题要求时间复杂度小，所以不能从头遍历。本文的思路是将删除节点i的后一节点j复制到i的位置上，然后将原本的j节点删除，即达到了删除节点i的效果。
特殊情况的考虑：如果要删除的节点是尾节点，没有下一节点，那么用上述的方法不可，这时候需要从链表的开始遍历，得到该节点的前序节点并完成删除操作。另外，如果链表中只有一个节点时，除了删除节点，还要将头节点设置为None。
代码实现：
class ListNode:
def __init__(self):
self.value = None
self.next_node = None
class Solution:
def delete_node(self,head_node,del_node):
if not(head_node and del_node):
return False
if del_node.next_node != None:#删除节点不是尾节点
if del_node == head_node:
head_node = del_node.next #如果删除的是头节点，首先把头节点重置（剑指offer思路中没有，自己思考所加）
del_node_next = del_node.next_node
del_node.value = del_node_next.value
del_node.next = del_node_next.next_node
del_node_next.value = None
del_node_next.next_node = None
elif head_node == del_node: #链表只有一个节点，即头节点，且删除该节点
head_node = None
del_node = None
else: #删除节点是尾结点，链表有多个节点
node = head_node
while node.next != del_node:
node = node.next
node.next = None
del_node = None
return head_node
运行结果：
暂未用实例进行 测试.....
题目二：删除重复的节点
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5。
思路：
这道题的思路是如果遇到重复的节点，则一直向后遍历，直到遇到第一个与重复节点不同的节点，然后将重复节点的前一节点与不重复 的第一个节点相连接，然后将node赋值为重复节点的前一节点进行下一次遍历。如果遇到的不是重复节点，则依次向后遍历。此外在遇到重复节点中有一种情况为头节点重复，此时需要额外将头节点的值重新修改，并且下一次遍历值为当前的不重复节点。
代码实现：
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteDuplication(self, pHead):
# write code here
if not pHead:
return
Prehead = None #初始的头节点的前节点为None
pNode = pHead
while pNode != None: #从头开始遍历
needDelete = False
if pNode.next != None and pNode.val == pNode.next.val:
needDelete = True
if not needDelete: #如果不需要删除，遍历到下一节点
Prehead = pNode
pNode = pNode.next
else:
value = pNode.val
toBeDelete = pNode
while (toBeDelete != None and toBeDelete.val == value):
#如果重复，一直向后遍历，直到第一个与value不同的节点出现结束
toBeDelete = toBeDelete.next
if Prehead == None: #考虑特殊情况，头节点重复
pHead = toBeDelete #将头节点赋值为不重复的第一个节点
pNode = toBeDelete #赋值pNode以便于下次while循环
continue #不再执行这一行代码之后的内容
else:
Prehead.next = toBeDelete #如果不是特殊情况，则将前节点的下一节点指向重复节点结束后的第一个不重复的节点
pNode = Prehead
#删除重复节点的情况下下一次要遍历的节点应该是toBeDelete的前一节点，因为该节点与删除的节点不同并不能代表其与下一个节点不同
return pHead #最后返回链表的头节点
运行结果：
提交结果
网友评论