如何从单链表的末尾找到第n个元素？

Question

下面的函数试图寻找nth到最后一个单向链表的元素.

例如:

如果元素是8->10->5->7->2->1->5->4->10->10结果是 7th最后一个节点是7.

任何人都可以帮助我解释这段代码是如何工作的,还是有更好更简单的方法？

LinkedListNode nthToLast(LinkedListNode head, int n) {
  if (head == null || n < 1) {
    return null;
  }

  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead
    if (p2 == null) {
      return null; // not found since list size < n
    }
    p2 = p2.next;
  }

  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

  return p1;
}

Answer 1

这个算法的关键是最初设置两个指针p1并p2分开n-1节点,所以我们想从列表的开头p2指向(n-1)th节点,然后我们移动p2直到它到达last列表的节点.一旦p2到达列表的末尾,p1将指向列表末尾的第n个节点.

我把解释内联作为评论.希望能帮助到你:

// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
  // If list does not exist or if there are no elements in the list,return NULL
  if (head == null || n < 1) {
    return null;
  }

  // make pointers p1 and p2 point to the start of the list.
  LinkedListNode p1 = head;
  LinkedListNode p2 = head;

  // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
  // so we want p2 to point to the (n-1)th node from the start of the list
  // then we move p2 till it reaches the last node of the list. 
  // Once p2 reaches end of the list p1 will be pointing to the nth node 
  // from the end of the list.

  // loop to move p2.
  for (int j = 0; j < n - 1; ++j) { 
   // while moving p2 check if it becomes NULL, that is if it reaches the end
   // of the list. That would mean the list has less than n nodes, so its not 
   // possible to find nth from last, so return NULL.
   if (p2 == null) {
       return null; 
   }
   // move p2 forward.
   p2 = p2.next;
  }

  // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
  // till p2 reaches the last node in the list.
  while (p2.next != null) {
    p1 = p1.next;
    p2 = p2.next;
  }

   // at this point p2 has reached the last node in the list and p1 will be
   // pointing to the nth node from the last..so return it.
   return p1;
 }

或者我们可以设置p1和p2分开n个节点而不是(n-1)然后移动p2到列表的末尾而不是移动到最后一个节点:

LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j < n ; ++j) { // make then n nodes apart.
    if (p2 == null) {
        return null;
    }
    p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
    p1 = p1.next;
    p2 = p2.next;
}
return p1;

Answer 2

您的算法的工作原理是首先创建对链接列表中两个节点分开的节点的引用.因此,在您的示例中,如果N为7,则将p1设置为8,将p2设置为4.

然后,它将每个节点引用前进到列表中的下一个节点,直到p2到达列表中的最后一个元素.同样,在您的示例中,这将是当p1为5且p2为10.此时,p1指的是列表中最后一个元素的第N个(由属性表示它们是N个节点分开).

Answer 3

你对这种方法有什么看法？

1. 计算链表的长度.
2. 来自head = linkedlist length的实际节点索引 - 给定索引;
3. 从头开始写一个函数travesre并获取上述索引的节点.

Answer 4

//this  is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{  
 if( temp->next != NULL)
   find( temp->next, k);
 if((c++) == k)       // c is initially declared as 1 and k is the node to find from last.
  cout<<temp->num<<' ';
}