lintcode_372. Delete Node in a Linked List

lintcode
372. Delete Node in a Linked List
설명: 삭 제 를 기다 리 는 노드 (표 머리 나 표 끝 이 아 닌) 를 지정 합 니 다.O (1) 시간 복잡 도 에서 이 링크 노드 를 삭제 하 십시오.
샘플: Linked list is 1 - > 2 - > 3 - > 4, and given node 3, delete the node in place 1 - > 2 - > 4
/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */

사고 1: 일반적인 방법 은 표 머리 부터 옮 겨 다 니 고 삭제 할 노드 를 찾 으 면 삭제 합 니 다. 시간 복잡 도 O (n) 이 고 이 문 제 는 표 머리 요 소 를 제시 하지 않 았 습 니 다.사고방식 2: 삭 제 될 노드 의 다음 노드 의 값 을 삭 제 될 노드 에 부여 하고 다음 노드, 시간 복잡 도 O (1) 를 삭제 하 며 헤더 요 소 를 제시 할 필요 가 없다 (삭 제 된 요소 가 끝 요소 라면 이런 방법 으로 삭제 할 수 없다 면 반드시 처음부터 체인 테이블 을 옮 겨 다 니 며 삭제 해 야 한다)
사고방식 2 코드 는 다음 과 같다.
public class Solution {
    /*
     * @param node: the node in the list should be deletedt
     * @return: nothing
     */
    public void deleteNode(ListNode node) {
        // write your code here
        if(node == null || node.next == null)
            return;
        node.val = node.next.val;  //  
        node.next = node.next.next; //            
    }
}

좋은 웹페이지 즐겨찾기