검 지 offer - 18. 체인 테이블 의 노드 삭제

주문서 에 링크 의 헤드 포인터 와 삭제 할 노드 의 값 을 주 고 함수 가 이 노드 를 삭제 하도록 정의 합 니 다.삭 제 된 링크 의 머리 노드 를 되 돌려 줍 니 다.
주의: 이 문 제 는 원제 에 비해 변경 되 었 습 니 다.
예시 1:
입력: head = [4, 5, 1, 9], val = 5 출력: [4, 1, 9] 설명: 링크 의 중간 값 이 5 인 두 번 째 노드 를 지정 하면 함 수 를 호출 한 후에 이 링크 는 4 - > 1 - > 9 로 변 합 니 다.
출처: 스냅 백 (LeetCode) 링크:https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteNode(self, head: ListNode, val: int) -> ListNode:
        if head.val == val: return head.next
        pre, cur = head, head.next
        while cur and cur.val != val:
            pre, cur = cur, cur.next
        if cur: pre.next = cur.next
        return head

검 지 offer 원제:
문제 1: O (1) 시간 내 에 링크 노드 를 삭제 합 니 다.주문서 에 링크 의 헤드 포인터 와 노드 포인터 에 게 함수 가 O (1) 시간 내 에 이 노드 를 삭제 하도록 정의 합 니 다.
문제 2: 정렬 된 링크 에서 중 복 된 노드 를 삭제 하 십시오. 예 를 들 어 1 - 2 - 3 - 3 - 4 - 5 는 중 복 된 노드 가 삭 제 된 후에 1 - 2 - 5 입 니 다.
문제 풀이 사고 1: 링크 요 소 를 목록 에 저장 한 다음 에 나타 난 횟수 가 1 이상 인 값 을 걸 러 내 고 나타 난 횟수 가 1 인 값 만 유지 한 다음 에 새로운 목록 을 링크 형식 으로 만 듭 니 다.

# _*_coding:utf-8 _*_

class ListNode:
    def __init__(self):
        self.value = None
        self.next_node = None

class Solution:
    def list_generate(self, lst):  #      
        """
            
        """
        if not lst:
            return None
        list_node = ListNode()
        list_node.value = lst[0]
        if len(lst) == 1:
            list_node.next_node = None
        else:
            list_node.next_node = self.list_generate(lst[1:])
        return list_node

    def find_node(self, node, target_value):
        """
                ，         
             ，        
        """
        if not target_value:
            return False
        while node:
            if node.value == target_value:
                return node
            node = node.next_node
        return False

    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


    def is_repeat(self, node):
        """
           ：            
        """
        if node.next_node:
            if node.value == node.next_node.value:
                return True
        return False

    def delete_repeat_node(self, head_node):
        """
           ：      
        """
        node = head_node
        flag = False
        """
        flag  ：  'a'->'a'，          'a',      flag                  
             ，          'a' ，  ，     flag    'a'     ，
        """
        while node:
            if solution.is_repeat(node):
            #       ，     node=node.next_node，            
                head_node = self.delete_node(head_node, node)
                flag = True
            else:
                if flag:
                    head_node = self.delete_node(head_node, node)
                    flag = False
                node = node.next_node
        return head_node


if __name__ == '__main__':
    solution = Solution()
    head_node = solution.list_generate(['a', 'a', 'a', 'b', 'c', 'e', 'd', 'd'])#     

    # ----------------------------------------------------
    #    ：       
    # target_value = 'a'
    # target_node = solution.find_node(head_node, target_value)
    # if target_node:
    #     print target_node.value
    # head_node = solution.delete_node(head_node, target_node)
    # ---------------------------------------------------

    # ---------------------------------------------------
    #    ：      
    head_node = solution.delete_repeat_node(head_node)
    # --------------------------------------------------

    #   ,     
    node = head_node
    if node:
        while node:
            print node.value,
            node = node.next_node
            if node:
                print '->',
    else:
        print 'wrong'