Tìm "Nth nút từ đầu" của danh sách được liên kết

Question

Điều này dường như trả về câu trả lời đúng, nhưng tôi không chắc đây có phải là cách tốt nhất để thực hiện mọi thứ hay không. Có vẻ như tôi đang truy cập các nút n đầu tiên quá nhiều lần. Bất kỳ đề xuất? Lưu ý rằng tôi phải làm điều này với một danh sách liên kết đơn lẻ.

Node *findNodeFromLast(Node *head, int n) 
{ 
    Node *currentNode; 
    Node *behindCurrent; 
    currentNode = head; 
    for(int i = 0; i < n; i++) { 
     if(currentNode->next) { 
      currentNode = currentNode->next; 
     } else { 
      return NULL; 
     } 
    } 

    behindCurrent = head; 
    while(currentNode->next) { 
     currentNode = currentNode->next; 
     behindCurrent = behindCurrent->next; 
    } 

    return behindCurrent; 
} 

Answer 1

Một cách khác để làm điều đó mà không ghé thăm các nút hai lần như sau:

Tạo một mảng trống rỗng kích thước n, một con trỏ vào mảng này bắt đầu từ chỉ số 0, và bắt đầu lặp lại từ đầu của danh sách liên kết. Mỗi lần bạn ghé thăm một nút lưu nó trong chỉ mục hiện tại của mảng và tiến lên con trỏ mảng. Khi bạn điền vào mảng, quấn quanh và ghi đè lên các phần tử bạn đã lưu trước đó. Khi bạn đến cuối danh sách, con trỏ sẽ trỏ đến phần tử n từ cuối danh sách.

Nhưng điều này cũng chỉ là một thuật toán O (n). Những gì bạn đang làm là tốt. Tôi thấy không có lý do thuyết phục để thay đổi nó.

Answer 2

Bạn có thể sử dụng danh sách được liên kết kép, danh sách được liên kết cũng lưu trữ địa chỉ của phụ huynh đó. Transversal dễ dàng hơn nhiều, vì bạn có thể bắt đầu ở cuối và làm việc theo cách của bạn để bắt đầu.

Answer 3

Thời gian chạy của bạn vẫn là O (n), vì vậy tôi không thấy có bất kỳ vấn đề gì với nó.

Về mặt khái niệm, bạn có thể chia danh sách thành hai phần: phần trước nút bạn quay lại và phần sau. Một trong những phần này sẽ phải được đi hai lần. Việc triển khai của bạn đã chọn lần đầu tiên, với lợi thế là không sử dụng thêm bộ nhớ (ngoài một vài biến tạm thời).

Cách khác, bạn có thể tạo ngăn xếp, đi bộ danh sách và đặt từng phần tử vào ngăn xếp, sau đó bật ra các mục n. Sau đó, bạn sẽ được đi bộ vào cuối danh sách hai lần, thay vì bắt đầu. Điều này có những bất lợi của việc lưu trữ danh sách trong bộ nhớ hai lần. (Bạn có thể làm cho ngăn xếp thông minh hơn một chút bằng cách chỉ lưu trữ các phần tử n và thả chúng xuống dưới cùng của ngăn xếp vì các phần tử mới được thêm vào; sau đó bạn chỉ sử dụng đủ không gian để lưu trữ n Nút.)

Tôi giả sử rằng bạn không thể thổi bay danh sách bằng cách đảo ngược nó tại chỗ. Sau đó, nó là bộ nhớ liên tục, vẫn O (n), vẫn đi bộ vào cuối danh sách hai lần.

Answer 4

Bắt đầu hai con trỏ. Di chuyển phần tử đầu tiên N phía trước và sau đó di chuyển từng phần tử con trỏ 1. Khi con trỏ đầu tiên đến cuối, con trỏ thứ hai sẽ trả lời.

CHỈNH SỬA: Có, nó giống như mã được đưa ra trong câu hỏi. Nhưng tôi cảm thấy mã giả làm cho nó rõ ràng hơn. Để trả lời câu hỏi, không có sự cố nào khác khi các thành phần N đầu tiên phải được truy cập hai lần. Nếu N thì không quan trọng. Nếu N lớn thì vòng lặp thứ hai sẽ nhỏ. Vì vậy, nó luôn luôn là một giải pháp O(n).

Answer 5

Đầu tiên đếm số lượng nút trong danh sách. Sau đó đi qua một lần nữa, đếm ra n nút ít hơn. Vẫn là một thuật toán O (n), điều đó là không thể tránh khỏi.

Answer 6

Node* fetchNNodeFrmLast(int arg) 
    { 
    Node *temp = head; 
    Node *nNode = head; 
    if(head == NULL || arg <= 0) 
    { 
     Printf("Either head is null or invalid number entered"); 
     return; 
    } 


    while(temp != NULL) 
    { 

     temp = temp->next; 
     if(arg > 1) 
     { 
      arg--; 

      continue; 
     }  
     nNode = nNode->next;  
    } 

    return nNode; 
} 

Answer 7

Tôi đang sử dụng biến tĩnh 'i' sẽ được tăng lên khi lùi lại từ cuối Danh sách. Giống như trong câu hỏi về vấn đề , về cơ bản chúng tôi sẽ theo dõi phần tử Nth bắt đầu từ cuối danh sách được liên kết. Đệ quy giúp chúng tôi theo dõi từ đầu.

static int i; 
public static void NthToLast(LinkedListNode head, int n) 
{ 
    if (head == null) 
     return; 

    NthToLast(head.Next, n); 
    i++; 
    if (n == i) 
    { 
    Console.WriteLine("Mth to last" + head.Data); 
    return; 
    } 

} 

Answer 8

của nó rất đơn giản .. mất hai con trỏ p1, p2 bắt đầu p2 sau p1 đã đi 'n' nút và để p1 du lịch tối đa last.the nút trỏ bởi p2 sẽ nút thứ n từ cuối

Answer 9

Duy trì cách nhau 2 nút con. Khi con trỏ thứ nhất đến đuôi, con trỏ thứ hai sẽ trỏ tới nút mong muốn.

Code:

typedef struct _node //define the list node 
{ 
    int i; 
    struct _node *next; 
} Node; 



Node * findNode(Node *listHead, int n) 
{ 
    Node *ptr1, *ptr2; // we need 2 pointers 
    ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially 

    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node) 
    { 
     if(n > 0) 
     { 
      ptr1 = ptr1->next; //increment only the 1st pointer 
      n--; 
     } 
     else 
     { 
      ptr1 = ptr1->next; //increment both pointers 
      ptr2 = ptr2->next; 
     } 
    } 
    return ptr2; //now return the ptr2 which points to the nth node from the tail 

}

Answer 10

Mã này có vẻ là rõ ràng hơn.

public Node<T> findNthNodeFromLast(int n) { 
    Node<T> current = head; 
    Node<T> findElement = head; 
    int length = 0; 
    while (current != null && current.next != null) { 
     length++; 
     if (length >= n) { 
      findElement = findElement.next; 
     } 
     current = current.next; 
    } 

    return findElement; 
} 

Answer 11

Sử dụng hai con trỏ pTemp và NthNode. Ban đầu, cả hai điểm vào nút đầu của danh sách. NthNode bắt đầu di chuyển chỉ sau khi di chuyển nTemp thực hiện n. Từ cả hai di chuyển về phía trước cho đến khi pTemp đến cuối danh sách. Kết quả là NthNode trỏ tới nút thứ n từ cuối danh sách liên kết.

public ListNode NthNodeFromEnd(int n){ 
     ListNode pTemp = head, NthNode = null; 
     for(int count=1; count<n;count++){ 
     if(pTemp!=null){ 
      pTemp = pTemp.getNext(); 
     } 
     } 
     while(pTemp!=null){ 
     if(NthNode==null){ 
      NthNode = head; 
     } 
     else{ 
      NthNode = NthNode.getNext(); 
     } 
     pTemp = pTemp.getNext(); 
     } 
     if(NthNode!=null){ 
     NthNode = NthNode.getNext(); 
     return NthNode; 
     } 
    return null; 
    } 

Tham khảo sách giáo khoa: "Cấu trúc dữ liệu và giải thuật Made Easy trong Java"