이 질문이 있습니다. L의 각 노드가 정수 키를 저장하고 L의 다음 노드를 가리키는 포인터가 단일 링크 된 목록 L이 제공됩니다. 마지막 노드에는 다음 노드는 NULL로 설정됩니다. 목록의 마지막 노드가 아닌 키 k를 저장하는 노드에 포인터 ptr이 제공됩니다. 주어진 ptr 목록에서 k를 지우는 방법을 보여줍니다. k가 들어있는 노드에 대한 포인터입니다; 귀하의 알고리즘은 시간 복잡성 O (1)을 가져야합니다. 즉, 목록의 길이와 독립적이어야합니다.단일 링크 된 목록에서 노드 삭제
두 배로 연결된 목록이있는 경우 O (1) 시간 복잡도 인 노드 을 삭제할 수 있음을 알고 있습니다. 단 하나의 링크 된 노드에서 노드를 삭제할 수있는 방법을 알고 있습니다. 명부? 노드 바로 앞에있는 노드를 찾으려면 모든 목록을 반복해야합니까? > B - -> C -
이 고려 연결된 목록으로 D>, 그리고 이제 우리는 B. 'PTR'을 제거해야 가정 해 봅시다 B에 PTR 및 PTR 사이
, 이것은 실패 할 수 있습니다. 'ptr'이 첫 번째 노드 인 경우 ptr.next에 헤드 포인트를 지정하면됩니다. 그러나 그것이 마지막 노드라면 꼬리를 '뒤로'이동할 수 없기 때문에 목록을 탐색하고 이전 노드를 추적해야합니다.
고마워요 : D 아주 명확하고 유용합니다 :) –
내가 아는, 스택 (LIFO)을 위해 그것을 수행하는 방법 - 삽입/O (1) 당신이 괜찮다면
하면, 데이터가 거꾸로 될 것이라고, 당신은 추가 할 수있는 마지막 항목 삭제 먼저 좋아해요.
예 : 일반적인 방법으로 list.insert(1)
list.insert(2)
list.insert(3)
이 같은 목록에있을 것입니다 : (1,2,3) 하지만 당신은 다음을 O (1) 필요한 경우 다음과 같이됩니다 : (3,2,1) - 마지막 항목 위치 1에, 그래서이 (루비 코드) 같은 것을 할 것이다 삭제됩니다
def delete
@head = @head.next
end
나는이 할당 것 같다. 그렇다면 속임수를 쓰지 마세요. 과정 자료를 검토하면 답이 간단해질 것입니다. 그것은 3 줄의 C 코드와 비슷합니다. 코드에 _ 특정 _ 문제가 없으면 답을주지 않겠습니다. –
이것은 불가능합니다. – aschepler
@StefanoSanfilippo 처음에는 과제가 아니며 다음 주에 중간 고사가 있었고 몇 가지 추가 문제를 해결하려고했습니다. 두 번째로 문제를 해결하지 않으면이 질문을 게시하지 않겠습니다.이들은 내 생각 : 만약 내가 두 번 링크 된 목록을 가지고, 노드에 포인터가있는 요소를 삭제하려면, 난 그냥 다음과 같이 할 수 있습니다 : ptr-> previous-> next = ptr-> next; 그러나 이것은 단 하나 연결된 목록에있는 경우가 아닙니다! –