//2.2实现一个算法,找出单向链表中倒数第k个结点。 //a不返回该元素,仅打印该值。 public static int nthToLast(LinkedListNode head, int k) { if (head == null) { return 0; } int i = nthToLast(head.next, k) + 1; if (i == k) { System.out.println(head.data); } return i; } //b使用c++,通过引用传值。这样一来,我们就可以返回结点值,而且也能通过传递指针更新计数器。 node* nthToLast(node* head, int k, int& i) { if (head == NULL) { return NULL; } node* nd = nthToLast(head->next, k, i); i = i + 1; if (i == k) { return head; } return nd; } //c创建包裹类 public class IntWrapper { public int value = 0; } LinkedListNode nthToLastR2(LinkedListNode head, int k, IntWrapper i) { if (head == null) { return null; } LinkedListNode node = nthToLastR2(head.next, k ,i); i.value = i.value + 1; if (i.value == k) { return head; } return node; }
我最喜欢下面这个
//d迭代法,使用两个指针p1,p2,将他们分别指向链表中的两个相隔为k个结点的结点。 LinkedListNode nthToLast(LinkedListNode head, int k) { if (k <= 0) { return null; } LinkedListNode p1 = head; LinkedListNode p2 = head; //将p2指向p1之后k个结点 for(int i = 0; i < k - 1; i++) { if (p2 == null) { return null; } p2 = p2.next; } if (p2 == null) { return null; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }