싱글 링크 목록에서 마지막 세 번째 요소 찾기 - 알고리즘

Question

싱글 링크 목록에서 3 번째 마지막 요소를 찾기 위해 Algo에서 생각하고 있습니다 (공간이 효율적이지 않습니다)
O (n) 시간 복잡도가있는 루프를 사용하여 ArrayList에있는 목록 [공간의 복잡성이 많이]
Arraylist의 크기를 찾고 (size-2) 인덱스 위치에서 요소 [필수 요소]를 검색하십시오. 안내해주세요 내 너 한테 이해를

을 할 경우 참고 내가 검색 다른
은 다음과 같습니다 두 개의 포인터를 넣고 3 elemen에 1 요소와 제 2 포인터 1 포인터를 유지 첫 번째 포인터가 가리키는 노드 [필수 노드]를 검색하십시오.

Answer 1

• 두 개의 포인터를 사용하십시오 : pointer-1 및 pointer-2

• pointer-1은 단일 연결 목록에서 세 번째 노드를 가리 킵니다.

  pointer-1 = node1->next->next; // point to 3rd nd 
  
  node1-->node2-->node3-->node4---> ...... -->node-last 
         ^
         | 
         pointer-1 
  

• 이제 첫 번째 노드 이제

  pointer-2 = node1; // point to 1st nd 
  
  node1-->node2-->node3-->node4---> ...... -->node-last 
  ^   ^
      |    | 
      pointer-2  pointer-1 
  

• , 마지막 노드에 pointer-1 점까지 루프에서 링크 된 목록에있는 여행, 루프도 포인터-2 업데이트 (모든 시간에 pointer-2 포인트를 설정 자신의 다음 노드)

  while (pointer-1->next!=NULL){// points to last node 
      pointer-1 = pointer-1 -> next; 
      pointer-2 = pointer-2 -> next; 
  } 
  
  When loop ends pointer-1 points to last-node, pointer-2 points to third last 
  
  node1-->node2-->........ ->node-l3-->node-l2-->node-last 
            ^    ^
            |     | 
            pointer-2   pointer-1 
  

이 작업에 s는 O (n) 번, 여기서 n은 링크 된 목록의 노드 수입니다.

Answer 2

링크 된 목록이 단독으로 링크되었으므로 링크 된 목록에서 링크를 이동해야합니다. 3 번째에서 마지막 요소가 무엇인지 알기 위해 끝나기 시작합니다. os O(n) (링크 된 목록의 세 번째 요소와 마지막 요소에 대한 포인터를 유지하지 않는 한) 시간은 불가피합니다.

2 포인터 아이디어는 일정한 공간을 사용합니다. ArrayList를 작성하면 더 많은 오버 헤드가 발생하고 더 많은 공간을 사용하므로 더 나은 옵션입니다.

Answer 3

두 개의 포인터를 얻으십시오. 펜실베니아 pB의 3 개 요소 이동 펜실바니아 발전 pB의 헤드에이 후

1->2->3->4-> .... ->99->100 
|  | 
pB pA 

을 펜실바니아 마지막 요소에 도달 할 때까지 동일한 루프 모두 포인터를 이동한다. 통과 하나가 될 것입니다 : 그 시점 Pb를에서

는

1->2->3->4-> .... ->98->99->100 
        |  | 
        pB  pA 

편집은 지난 3 요소를 가리키는 것

여기

while(pA->next!=null){ 
    pA = pA->next; 
    pB = pB->next; 
} 

(PB)은 3 할 것이다 마지막

Answer 4

대안적인 도면이이 O는 (N)

않더라도 해결 빈 배열 (N), 0이 배열에 대한 포인터를 시작하고,도 링크드리스트의 시작 부분에서 시작 만들기 . 노드를 방문 할 때마다 배열의 현재 색인에 노드를 저장하고 배열 포인터를 전진시킵니다. 배열의 노드를 계속 채우십시오. 배열의 끝에 도달하면 처음부터 다시 시작하여 덮어 씁니다. 지금 당신은 목록의 마지막 말 끝 : 당신은 그냥 list.get '에 갈 수 있도록

실제로

Answer 5

, 자바 LinkedList이 크기의 트랙, 유지의 포인터 n 번째 elemtn (는 list.size을 (종료 후) -2) ',하지만 링크 된 목록이 생성 된 경우 다음을 수행합니다.

값의 배열을 유지하십시오. 목록을 탐색 할 때 값을 array[i%3]에 추가하십시오. 더 이상 값이 없으면 array[(i-2)%3]에 값을 반환하십시오.

Answer 6

내가해야 할 첫 번째 일은 당신이 단독으로 링크 된 목록의 사용을 재검토하도록 요청하는 것입니다. 왜 ArrayList에 데이터를 저장하지 않는가? 그것은 당신이 원하는 것처럼 보이는 모든 일을합니다. 그래서 그것은 내장되어있어서 대부분의 사람들이 쓰는 것과 비교하여 상대적으로 효율적입니다.

링크 된 목록을 사용하기로 결심했다면 3 번째 마지막 요소 (tle)에 대한 직접 포인터를 유지하는 것이 좋습니다. 삽입은 쉽습니다 - 그들이 tle 앞에 올 경우 아무 것도하지 마십시오. 이후에 있다면, 다음 포인터로 포인터를 이동하십시오. 제거는 더 많은 번거 로움이 있지만 대부분은 그렇지 않습니다. 그 썰매 앞에서 제거가 일어나면, 그것은 여전히 ​​콧소리입니다. 성가신 상황은 제거 할 요소가 tle 이상인 경우입니다.이 경우 현재 노드의 next() 참조가 처음부터 끝까지 반복 될 때까지 반복됩니다. 현재 노드가 새로운 트 레가되고 제거를 계속할 수 있습니다. 이 작업 레벨을 호출하는 노드는 세 개 뿐이므로 목록이 꽤 큰 경우 대부분의 경우에 대부분의 작업을 수행 할 것입니다.

최종 옵션은 끝에서 제거가 자주 발생하는 경우 목록을 앞뒤로 유지하는 것입니다. 그런 다음 유지 보수 목적으로 앞쪽에서 세 번째가됩니다.

Answer 7

//We take here two pointers pNode and qNode both initial points to head 
    //pNode traverse till end of list and the qNode will only traverse when difference 
    // between the count and position is grater than 0 and pthNode increments once 
    // in each loop 
    static ListNode nthNode(int pos){ 
    ListNode pNode=head; 
    ListNode qNode=head; 
    int count =0; 
    while(qNode!=null){ 
     count++; 
     if(count - pos > 0) 
      pNode=pNode.next; 
     qNode=qNode.next; 
    } 
    return pNode; 
}