剑指offer 面试18题

面试18题：

题目：删除链表中的节点

题一：在O(1)时间内删除链表节点。给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。

解题思路：我们要删除节点i,先把i的下一个节点j的内容复制到i,然后把i的指针指向节点j的下一个节点。此时再删除节点j,其效果等同于把节点i删除了。

解题代码：

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:

            del_next_node=del_node.next_node

            del_node.value=del_next_node.value

            del_node.next_node=del_next_node.next_node

            del_next_node.value=None

            del_next_node.next_node=None

        #链表只要一个节点，删除头节点（也是尾节点）

        elif del_node==head_node:

            head_node=None

            del_node = None

        #链表中有多个节点，删除尾节点

        else:

            node=head_node

            while node.next_node!=del_node:

                node=node.next_node

            node.next_node=None

            del_node=None

        return head_node

题目：删除链表中重复的节点。

题：在一个排序的链表中，请删除重复的节点，如1-2-3-3-4-4-5在重复的节点被删除后为1-2-5。

解题思路一：将链表元素保存在列表中，然后过滤掉出现次数大于1的值，只保留出现次数为1的值，再将新的列表建成链表的形式。

解题代码：

# -*- coding:utf-8 -*-

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def deleteDuplication(self, pHead):

        # write code here

        res=[]

        while pHead:

            res.append(pHead.val)

            pHead=pHead.next

        res=list(filter(lambda c:res.count(c)==1,res))

        newList=ListNode(0)

        pre=newList

        for i in res:

            node=ListNode(i)

            pre.next=node

            pre=pre.next

        return newList.next
            

解题思路二：运用链表的操作，确保将重复的节点略过，始终连接不重复的值。

解题代码：

# -*- coding:utf-8 -*-

# class ListNode:

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution:

    def deleteDuplication(self, pHead):

        # write code here

        first=ListNode(-1)

        first.next=pHead

        last=first

        while pHead and pHead.next:

            if pHead.val == pHead.next.val:

                val=pHead.val

                while pHead and pHead.val==val:

                    pHead=pHead.next

                last.next=pHead

            else:

                last=pHead

                pHead=pHead.next

        return first.next