×

Loading...
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。
Ad by
  • 最优利率和cashback可以申请特批,好信用好收入offer更好。请点链接扫码加微信咨询,Scotiabank -- Nick Zhang 6478812600。

本题标准答案(总分20,看看你能得几分)

本文发表在 rolia.net 枫下论坛We can assume the single link list has been defined as below:

template <class T> // Don't use template -2
class SLL // Single link list
{
public:
T current;
SLL<T> * next;
:
:
:
};

The following is the codes for return the nth element from the end of the list:

template <class T>
T * Lastnth(SLL<class T> * const begin, const int step )
// to find the last 3rd, call
// target = (T *)lastnth( begin, 3);
// Time complexity is O(n) // Other method with bigger complexity -5
{

if ( NULL == begin || step <= 0) return NULL; // Don't check parameter -2
// Empty linked list or wrong parameter
if (listclosed( begin)) return NULL; // Don't check closed link -5
// if it's a Closed link list, return NULL,
SLL<T> *b,*f; // f: Fore b:Back
int n = step;
b = f = begin;
while ( f ){
if ( --n > 0 ) f = f->next;
else break;
}
if ( !f ) // Withour consider length < n; n = 0, -3
return &(b->current);
// step == 0 will return the The last element
// If no more than n elements in the link,
// default we return the first element
// If we want return NULL when less than n elements
// modify the above to :
/**
return (n ? NULL : &(b->current);
// n == 0 : n elements, return the first one
// n > 0 : less than n elements, return NULL
// We use red color in test case for this setting
**/

while ( f ) {
f = f->next;
b = b->next;
}
return (void* )&(b->current);
}

Bool listclosed(SLL<class T> * const begin) // Time complexity is O(n)
// If consider link is closed, but time complexity bigger than O(n); -2
{
if ( NULL == begin) return TRUE;
SLL<T> * s, * f; // s: slow, f: fast
s = f = begin;
while (1) {
f = f-> next;
if ( f == s) return TRUE;
else if (f == NULL) return FALSE;
f = f-> next;
if ( f == s) return TRUE;
else if (f == NULL) return FALSE;
s = s->next;
// f moved in the double speed as s, if the list is
// closed, sooner or later, f will pull up to s
}
}更多精彩文章及讨论,请光临枫下论坛 rolia.net
Report

Replies, comments and Discussions:

  • 工作学习 / 专业技术讨论 / 单向链表, 如何找到倒数第3个结点?
    • 设计一个堆栈,一直push,push,push,push,push,push,push,push......然后倒底之后再Pop三次
    • 应该有要求只能LOOP一遍: 2个临时NODE, N1从HEAD前移2步到第3节点, 这时N2从HEAD与N1一起前移直至N1到底, 这时的N2就是倒数第3个结点 - N2一直落后N1两个节点.
      • 这个也好
    • 擴大為倒數M,兩個指針,一個先前走M步; 然後,兩個指針開始一起移動,當先走的指針到链表尾時,另一個指針就是答案. 算法複雜度為O(N).
      • 这个最好
      • Another same way is declare a queue with max depth of 3, push the node to the queue when traveling, and pop the first one from queue when done.
    • 如何remove重复的结点?
    • 什么样的需求导致你要remove 倒是第三个节点?这问题有点本末倒置了吧。
      • 他好像没说要remove 倒是第三个节点......
      • 不同的问题, 是remove链表中重复的结点。
    • 本题标准答案(总分20,看看你能得几分)
      本文发表在 rolia.net 枫下论坛We can assume the single link list has been defined as below:

      template <class T> // Don't use template -2
      class SLL // Single link list
      {
      public:
      T current;
      SLL<T> * next;
      :
      :
      :
      };

      The following is the codes for return the nth element from the end of the list:

      template <class T>
      T * Lastnth(SLL<class T> * const begin, const int step )
      // to find the last 3rd, call
      // target = (T *)lastnth( begin, 3);
      // Time complexity is O(n) // Other method with bigger complexity -5
      {

      if ( NULL == begin || step <= 0) return NULL; // Don't check parameter -2
      // Empty linked list or wrong parameter
      if (listclosed( begin)) return NULL; // Don't check closed link -5
      // if it's a Closed link list, return NULL,
      SLL<T> *b,*f; // f: Fore b:Back
      int n = step;
      b = f = begin;
      while ( f ){
      if ( --n > 0 ) f = f->next;
      else break;
      }
      if ( !f ) // Withour consider length < n; n = 0, -3
      return &(b->current);
      // step == 0 will return the The last element
      // If no more than n elements in the link,
      // default we return the first element
      // If we want return NULL when less than n elements
      // modify the above to :
      /**
      return (n ? NULL : &(b->current);
      // n == 0 : n elements, return the first one
      // n > 0 : less than n elements, return NULL
      // We use red color in test case for this setting
      **/

      while ( f ) {
      f = f->next;
      b = b->next;
      }
      return (void* )&(b->current);
      }

      Bool listclosed(SLL<class T> * const begin) // Time complexity is O(n)
      // If consider link is closed, but time complexity bigger than O(n); -2
      {
      if ( NULL == begin) return TRUE;
      SLL<T> * s, * f; // s: slow, f: fast
      s = f = begin;
      while (1) {
      f = f-> next;
      if ( f == s) return TRUE;
      else if (f == NULL) return FALSE;
      f = f-> next;
      if ( f == s) return TRUE;
      else if (f == NULL) return FALSE;
      s = s->next;
      // f moved in the double speed as s, if the list is
      // closed, sooner or later, f will pull up to s
      }
      }更多精彩文章及讨论,请光临枫下论坛 rolia.net