검지 offer 2 판 (Python 3) - 면접 문제 18: 링크 에서 중복 되 는 노드 삭제

제2 장 면접 에 필요 한 기초 지식
제3 장 고 품질의 코드
면접 문제
    면접 문제 18: 링크 에서 중복 되 는 노드 삭제
면접 문제 19: 정규 표현 식 일치
면접 문제 20: 수 치 를 나타 내 는 문자열
면접 문제
면접 문제
면접 문제 23: 링크 중간 고리 의 입구
면접 문제
제4 장 면접 문 제 를 해결 하 는 사고
제5 장 시간 과 공간 효율 최적화
제6 장 면접 에서 의 각종 능력
제7 장 두 면접 사례
제목 설명예 를 들 어 링크 1 - > 2 - > 3 - > 3 - > 4 - > 5 처리 후 1 - > 2 - > 5 입 니 다.
문제 풀이 의 방향 은 8195 ℃ 이 고 8195 ℃ 이다. 중복 노드 는 모두 삭제 해 야 하기 때문에 특히 머리 결점 이 중복 되 었 을 때 처리 하기 어렵다.재 귀 할 때 시스템 스 택 을 사용 하려 면 O (n) 의 공간 복잡 도가 필요 합 니까? 아니면 비 재 귀 를 사용 하 는 것 이 좋 습 니 다.『 8195 』 는 하나의 노드 가 머리 를 가리 키 는 노드 를 새로 만 들 수 있 습 니 다. 그러면 머리 결점 의 처 리 는 일반 노드 와 같 습 니 다.
실전
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or not pHead.next:
            return pHead
        
        new_head = ListNode(pHead.val-1)
        pre, p = new_head, pHead
        pre.next = p
        flag = False
        while p.next:
            if p.val == p.next.val:
                flag = True
            elif flag:
                pre.next = p.next
                flag = False
            else:
                pre = p
                flag = False
            p = p.next
        if flag:
            pre.next = p.next
        return new_head.next

좋은 웹페이지 즐겨찾기