从链接列表的末尾查找“第n个节点”

另一种不访问两次节点的方法如下:

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

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

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

编辑 :是的,它与问题中给出的代码基本相同。但我觉得伪代码更清楚了。要回答这个问题,没有其他的方法能比第一个更有效。 n 元素必须访问两次。如果 n 很小,没关系。如果 n 如果是大的,则第二个循环将是小的。所以它总是一个 O(n) 解决方案。

保持两个指针和节点之间的距离。当第一个指针到达尾部时,第二个指针将指向所需的节点。

代码:

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

}

我使用的静态变量“i”将递增 而从列表的末尾进行回溯。就像在 问题陈述,我们基本上会跟踪第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; 
     }

}

你的跑步时间还是O(N),所以我看不出有什么问题。

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

或者,您可以创建一个堆栈,浏览列表并将每个元素放入堆栈,然后弹出n个项。然后你将走到列表的末尾两次,而不是开始。这样做的缺点是将列表存储在内存中两次。(您可以通过只存储n个元素并在添加新元素时将它们从堆栈底部放下来,从而使堆栈更智能;然后您只需要使用足够的空间来存储n个节点。)

我假设你不能把清单倒过来把它吹走。然后是持续的记忆,仍然是O(N),仍然走在列表的末尾两次。

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

使用双指针ptemp和nthnode。最初,这两个节点都指向列表的头节点。nthnode仅在ptemp进行n次移动后才开始移动。从两者向前移动,直到ptemp到达列表末尾。结果,nth node从链接列表的末尾指向nth节点。

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

参考教材:“Java中的数据结构和算法”

您可以使用双重链接列表,它是一个也存储其父级地址的链接列表。横向比较容易,因为你可以从结尾开始,一直到开头。

首先计算列表中的节点数。然后再次遍历,计数n个更少的节点。仍然是一个O(N)算法,这是不可避免的。

很简单…… 取两个指针p1,p2 在p1移动“n”节点后启动p2,让p1移动到最后一个节点。p2指向的节点将是从最后一个节点开始的第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;
}