面试题 18：删除链表的节点

题目一：在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  #最后返回链表的头节点

运行结果：