查找链表的“从末尾开始的第N个节点”

This seems to be returning the correct answer, but I'm not sure if this is really the best way to go about things. It seems like I'm visiting the first n nodes too many times. Any suggestions? Note that I have to do this with a singly linked list.

这似乎正在回答正确的答案，但我不确定这是否真的是最好的方法。好像我正在访问前n个节点太多次了。有什么建议么？请注意，我必须使用单链表进行此操作。

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;
}

11 个解决方案

#1

Another way to do it without visiting nodes twice is as follows:

在不访问节点两次的情况下执行此操作的另一种方法如下：

Create an empty array of size n, a pointer into this array starting at index 0, and start iterating from the beginning of the linked list. Every time you visit a node store it in the current index of the array and advance the array pointer. When you fill the array, wrap around and overwrite the elements you stored before. When you reach the end of the list, the pointer will be pointing at the element n from the end of the list.

创建一个大小为n的空数组，从索引0开始指向此数组的指针，并从链表的开头开始迭代。每次访问节点时，都会将其存储在数组的当前索引中并使数组指针前进。填充数组时，环绕并覆盖之前存储的元素。到达列表末尾时，指针将指向列表末尾的元素n。

But this also is just an O(n) algorithm. What you are currently doing is fine. I see no compelling reason to change it.

但这也只是一个O（n）算法。你现在做的很好。我认为没有令人信服的理由来改变它。

#2

Start an two pointers. Move the first one N elements ahead and then move each pointer 1 element. When the first pointer reaches the end, second pointer will give the answer.

开始两个指针。向前移动第一个N个元素，然后移动每个指针1个元素。当第一个指针到达结尾时，第二个指针将给出答案。

EDIT : Yes, it is pretty much the same code as given in the question. But I feel the pseudo code make it clearer. To answer the question, there is no other go as first N elements have to be visited twice. If N is small it doesn't matter. If N is large then the second loop will be small. So it is always an O(n) solution.

编辑：是的，它几乎与问题中给出的代码相同。但我觉得伪代码让它更清晰。要回答这个问题，没有其他的可以去，因为前N个元素必须被访问两次。如果N很小则无关紧要。如果N很大，则第二个循环将很小。所以它总是一个O（n）解决方案。

#3

Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

保持2个节点间的2个指针。当第一个指针到达尾部时，第二个指针将指向所需的节点。

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

}

}

#4

I am using a static variable 'i' which will be incremented while backtracking from the end of the List. Like in the problem statement, we would basically tracking the Nth element starting from the end of linked list. Recursion helps us track from the end.

我正在使用一个静态变量'i'，它将从List的末尾回溯时递增。就像在问题陈述中一样，我们基本上会从链表的末尾开始跟踪第N个元素。递归有助于我们从最终进行跟踪。

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; 
     }

}

#5

Your running time is still O(n), so I don't see that there's any problem with it.

你的运行时间仍然是O（n），所以我没有看到它有任何问题。

Conceptually, you can divide the list into two parts: the part before the node you're returning, and the part after. One of these parts will have to be walked twice. Your implementation has chosen the first, at the advantage of no extra memory use (other than a couple temporary variables).

从概念上讲，您可以将列表分为两部分：返回节点之前的部分和之后的部分。其中一个部分必须走两次。您的实现选择了第一个，没有额外的内存使用（除了几个临时变量）。

Alternatively, you could create a stack, walk the list and put each element into the stack, and then pop off n items. Then you'd be walking the end of the list twice, instead of the beginning. This has the disadvantage of storing the list in memory twice. (You could make the stack a little smarter by only storing n elements and dropping them off the bottom of the stack as new ones are added; then you're only using enough space to store n Nodes.)

或者，您可以创建一个堆栈，遍历列表并将每个元素放入堆栈，然后弹出n个项目。然后你将走两​​次列表的末尾，而不是开头。这具有将列表存储在存储器中两次的缺点。 （你可以通过只存储n个元素并在添加新元素时将它们从堆栈底部删除来使堆栈变得更加智能;然后你只使用足够的空间来存储n个节点。）

I'm assuming that you can't blow away the list by reversing it in place. Then it's constant memory, still O(n), still walking the end of the list twice.

我假设你不能通过将它反转到位来吹走它。然后它是常量内存，仍然是O（n），仍然在列表的末尾两次。

#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;   
}

#7

Use two pointer pTemp and NthNode. Initially, both points to head node of the list. NthNode starts moving only after pTemp made n moves. From the both moves forward until pTemp reaches end of the list. As a result NthNode points to nth node from the end of the linked list.

使用两个指针pTemp和NthNode。最初，两者都指向列表的头节点。只有在pTemp进行n次移动后，NthNode才开始移动。从两者向前移动直到pTemp到达列表的末尾。结果，NthNode指向链表末尾的第n个节点。

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;
  }

Refer TextBook : "Data Structure and Algorithms Made Easy in Java"

参考TextBook：“Java中的数据结构和算法变得简单”

#8

You could use a doubly linked list, which is a linked list that also stores the address of it's parent. Transversal is much easier, since you can start at the end and work your way to the beginning.

您可以使用双向链表，这是一个链表，也存储了它的父地址。横向更容易，因为你可以从最后开始并按照自己的方式开始。

#9

First count the number of nodes in the list. Then traverse again, counting off n less nodes. Still an O(n) algorithm, that's unavoidable.

首先计算列表中的节点数。然后再次遍历，计算n个较少的节点。仍然是O（n）算法，这是不可避免的。

#10

its very simple.. take two pointers p1,p2 start p2 after p1 has travelled 'n' nodes and let p1 travel upto last.the node pointed by p2 will be nth node from last

非常简单..取两个指针p1，p2在p1经过“n”个节点后开始p2，让p1向上移动到最后.p2指向的节点将是最后一个节点

#11

This code seems to be more clear.

这段代码似乎更清楚。

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;
}