1.概述
鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。
当我们用一个指针遍历链表不能解决问题的时 候 ，可以尝试用两个指针来遍历链表可以让其 中一个指针遍历的速度快一些（比如一次在链表上走两步），或者让它先在链表上走若千步。
2.问题
输入一个链表，输出该链表中倒数第k个结点。
3.思路1
为了得到倒数第k个节点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是我们从链表节点的定义可以看出，本题中的链表是单向链表，单向链表的节点只有从前往后的指针而没有从后往前的指针，因此这种思路行不通。
4.思路2
删除从列表开头数起的第(L-n+1)个结点,其中L是列表的长度,只要我们找到列表的长度L,这个问题就很容易解决，首先我们将添加一个哑结点作为辅助,该结点位于列表头部哑结点用来简化某些极端情况,例如列表中只含有一个结点，或需要删除列表的头部。在第一次遍历中,我们找出列表的长度L。然后设置一个指向哑结点的指针,并移动它遍历列表, 直至它到达第(L-n)个结点那里,我们把第(L-n)个结点的next指针重新链接至第(-n+2)个结点,完成这个算法。
也就是说我们需要遍历链表两次，第一次统计出链表中节点的个数，第二次就能找到倒数第A个节点。但是当我们把这种思路解释给面试官之后，他会告诉我们他期待的解法只需要遍历链表一次
public static void main(String[] args) {
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);
FindKthToTail(head,2);
}
public static ListNode FindKthToTail(ListNode head, int k) {
if(head==null){
return null;
}
int count=1;
ListNode old=head;
while(head.next!=null){
head=head.next;
count++;
}
if(k>count){
return null;
}
for(int i=0;i<count-k;i++){
old=old.next;
}
return old;
}
}
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x; }
}
思路3
我们可以定义两个指针。第一个指针从链表的头指针开始遍历向前走k-1，第二个指针保持不动；从第k步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k-1，当第一个（走在前面的）指针到达链表的尾结点时，第二个指针（走在后面的）指针正好是倒数第k个结点。
public ListNode removeNthFromEnd(ListNode head, int n) {
// 输入的链表不能为空，并且k大于0
if (n < 1 || head == null) {
return null;
}
// 指向头结点
ListNode pointer = head;
// 倒数第k个结点与倒数第一个结点相隔k-1个位置
// pointer先走k-1个位置
for (int i = 1; i < n; i++) {
// 说明还有结点
if (pointer.next != null) {
pointer = pointer.next;
}
// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
else {
// 返回结果
return null;
}
}
// pointer还没有走到链表的末尾，那么pointer和head一起走，
// 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
while (pointer.next != null) {
head = head.next;
pointer = pointer.next;
}
// 返回结果
return head;
}
/* class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
第二种写法
public static ListNode FindKthToTail(ListNode head,int k) {
if(head == null) return null;
ListNode p1 = head,p2 = head;
while (k>0 && p2 != null){
p2 = p2.next;
k--;
}
//p2 指向head说明k<=0,p2==null && k>0说明 k超过了链表的长度
if(p2 == head || (p2 == null && k>0)) return null;
while (p2!=null){
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
相关题目
求链表的中间节点。如果链表中的节点总数为奇数，则返回中间节点；如果节点总数是偶数，则返回中间两个节点的任意一个。为了解决这个问题，我们也可以定义两个指针，同吋从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。
当我们用一个指针 遍 历 链 表 不 能 解 决 问 题 的 时 候 ，可以尝试用两个指针 来 遍 历 链 表 可 以 让 其 中 一 个 指 针 遍 历 的 速 度 快 一 些 （比如一次在链表上 走 两 步 ），或者让它先在链表上走若千步。
LeetCode
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
public ListNode removeNthFromEnd(ListNode head, int n) {
// 输入的链表不能为空，并且k大于0
if (n < 1 || head == null) {
return null;
}
// 指向头结点
ListNode pointer = head;
// 倒数第k个结点与倒数第一个结点相隔k-1个位置
// pointer先走k-1个位置
for (int i = 1; i < n; i++) {
// 说明还有结点
if (pointer.next != null) {
pointer = pointer.next;
}
// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
else {
// 返回结果
return null;
}
}
// pointer还没有走到链表的末尾，那么pointer和head一起走，
// 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
while (pointer.next != null) {
head = head.next;
pointer = pointer.next;
}
// 返回结果
return head;
}
原文地址https://mp.weixin.qq.com/s/mDXCcbq_zdlfEjnX1sQi0g
京公网安备 11010502036488号