设计一个复杂度为n的算法找到链表倒数第m个元素。最后一个元素假定是倒数第0个。
//节点定义: static class Node{ int val; Node next; } //得到倒数第k个节点。 public Node getKth(Node node, int m){ if (node == null) return null; Node p1 = node, p2 = node; int index = 0; while (p2.next != null){ if (++index <= m){ p2 = p2.next; } else { p1 = p1.next; p2 = p2.next; } } if (index < m) //链表长度小于等于k。 return null; return p1; }
// 因为m可以为0,所以辅助指针temp先走m+1步,然后temp和target同速度前进, // 当temp=null时,target所指即为倒数第m个元素 public static class Node { int value; Node next; public Node(int n) { this.value = n; this.next = null; } } // 查找链表中倒数第m个节点 m>=0 public static Node searchKthLastNode(Node head, int k) { if (head == null || k < 0) return head; if (k >= getListLength(head)) return null; Node target = head; Node temp = head; for (int i = 0; i <= k; i++) { temp = temp.next; } // n-k while (temp != null) { target = target.next; temp = temp.next; } temp = null; target.next = null; System.out.print("target.value: " + target.value + " "); return target; }