给定一个链表, 删除链表的倒数第 n 个节点, 并且返回链表的头结点.
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后, 链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的.
进阶:
你能尝试使用一趟扫描实现吗?
解法:
思路: 算法是只做了一趟扫描, 初始化两个节点, 先让一个节点从头开始走 n 个位置, 然后两个点再同时开始走, 走到一个节点到了最后, 则另一个节点就是所要删除的节点的位置.
- /**
- * Definition for singly-linked list.
- * public class ListNode {
- * int val;
- * ListNode next;
- * ListNode(int x) { val = x; }
- * }
- */
- class Solution {
- public ListNode removeNthFromEnd(ListNode head, int n) {
- ListNode p=head;
- ListNode q=head;
- if(head==null){
- return head;
- }
- for(int i=0;i<n;i++){
- q=q.next;
- }
- if(q==null){
- head=head.next;
- return head;
- }
- while(q.next!=null){
- q=q.next;
- p=p.next;
- }
- p.next=p.next.next;
- return head;
- }
- }
BB 一句:
试试 C 和 c++ 实现.
来源: http://www.jianshu.com/p/21473dd74e46