1 <?php 2 #查找链表倒数第i个节点,倒数第0个为最后一个节点 3 class Node { 4 public $data = null; 5 public $next = null; 6 } 7 8 #第一种方法，先算出链表总长，然后向后寻找n-i个节点 9 function last_i($head, $i) { 10 $cnode = $head; 11 $n = 0; 12 while ($cnode != null) { 13 $n++; 14 $cnode = $cnode->next; 15 } 16 17 $j = 1; 18 $cnode = $head; 19 while ($j < $n - $i) { 20 $j++; 21 $cnode = $cnode->next; 22 } 23 24 return $cnode; 25 } 26 27 #第二种方法，使用两个指针同时移动 28 function last_i_2($head, $i) { 29 $p1 = $head; 30 $p2 = $head; 31 $k = 0; 32 33 while ($k < $i) { 34 $p1 = $p1->next; 35 $k++; 36 } 37 38 while (($p1 = $p1->next) != null) { 39 $p2 = $p2->next; 40 } 41 42 return $p2; 43 } 44 45 $head = new Node(); 46 $n1 = new Node(); 47 $n2 = new Node(); 48 $n3 = new Node(); 49 $n4 = new Node(); 50 $head->data = 0; 51 $n1->data = 1; 52 $n2->data = 2; 53 $n3->data = 3; 54 $n4->data = 4; 55 $head->next = $n1; 56 $n1->next = $n2; 57 $n2->next = $n3; 58 $n3->next = $n4; 59 60 echo last_i($head, 2)->data . "<br>"; 61 echo last_i_2($head, 2)->data; 62 ?>
2
2