מריה בוטוסוב

נתונה רשימה מקושרת חד-כיוונית. צריך למצוא מיהו האיבר במיקום ה – n מסוף הרשימה. כאשר יש להחזיר תשובה מיד כאשר מגיעים לאיבר האחרון ברשימה.

נתונה רשימה מקושרת חד-כיוונית.

צריך למצוא מיהו האיבר במיקום ה – n מסוף הרשימה.

כאשר יש להחזיר תשובה מיד כאשר מגיעים לאיבר האחרון ברשימה.


static LinkedListNode nthToLast(LinkedListNode head, int k, ref i) {
//We recurses through the linked list. When it hits the end,
// the method passes back a counter set to 0
 if (head = null) { 
    return null;
 }
 //Each parent call adds 1 to this counter.
 LinkedListNode node =  nthToLast(head.next, k, ref i);
 i++;
//When the counter equals k, 
//we know we have reached the kth to last element
 if(i==k) { 
    return head;
 }
 return node;
}

הבעיתיות בקוד הזה שלמרות זמן ריצה (O(n , הוא לוקח גם (O(n  זיכרון בגלל רקורסיה, שפחות טוב.
יש אפשרות לשפר אותו ולהיות לא רקורסיבי (במקרה הזה הוא יקח  (O(n זמן ריצה ו  (O(1 זיכרון:


LinkedListNode nthToLast(LinkedListNode head, int k) {
 if(k<0) return null;

 LinkedListNode p1 = head;
 LinkedListNode p2 = head;
 
 //Move p2 forward k nodes into the list.
 for(int i = 0; i < k - 1; i++)
 {
    if(p2 == null) return null; //error check
    p2 = p2.next;
 }
 if(p2 == null) return null;

 //Now, move p1 and p2 at the same speed. When p2 hits the end, 
 //p1 will be at the right element
 while (p2.next !=null) {
      p1 = p1.next;
      p2 = p2.next;
 }
 return p1;
}