검 지 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'
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
\ # 데이터 구조 와 알고리즘 학습 노트 \ # 검 지 제공 42: 단어 순 서 를 뒤 집기 + 테스트 사례 (자바, C / C +)2019.1.2 검 지 Offer 는 제로 브러시 개인 노트 정리 (66 문제 전) 디 렉 터 리 전송 문 에서 인터넷 에 서 는 원 서 를 포함 한 많은 방법 이 문장 을 두 번 뒤 집 는 것 이다. 첫 번...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.