给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

用两个节点fast和slow，先让fast走n步，然后slow和fast一起走，等fast走到最后一个节点时，slow所在位置就是要删除的前一个节点。其他注意的就是抠边界了。

1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { val = x; } 7  * } 8  */ 9 class Solution {10     public ListNode removeNthFromEnd(ListNode head, int n) {11         ListNode fast = head,slow = head;12         13         while(n > 0){14             n--;15             fast = fast.next;16         }17         while(fast!=null && fast.next!=null){18             fast = fast.next;19             slow = slow.next;20         }21         if(fast == null){//fast为空有两种情形1.[1] n = 1   2.[1,2,3,4] n = 4分别对应下面的else 和 if22             if(head != null && head.next!=null){23                 head = head.next;24                 return head;25             }else{26                 head = null;27                 return head;28             }29             30         }31             fast = slow.next;32             slow.next = fast.next;33         return head;34     }35 }

2019-04-17 21:59:17