1
2
3
4
5
6
7
8
Given a linked list, remove the nth node from the end of list and return its head.
For example,
   Given linked list: 1->2->3->4->5, and n = 2.
 
   After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
Given n will always be valid.
Try to do this in one pass.

题意：删除倒数第N个节点。尽量一次遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head==null || n<1)return head;
        ListNode cur=head;
        while(cur!=null){
            n--;
            cur=cur.next;
        }
        if(n==0)head=head.next;
        if(n<0){
            cur=head;
            while(++n!=0){
                cur=cur.next;
            }
            cur.next=cur.next.next;
        }
        return head;
         
    }
}

PS:左老师提供的一种找倒数第K个的思路。先遍历一遍，同时K--，最后判断K的大小。K==0说明要删除的是头结点。K>0，说明K不对。K<0的时候，再从头走一遍，不过此时K++，K=0的时候也就找到了第K-1个。此时直接删除就行。

【方法2】网上的快慢指针法。fast先走K-1步。然后slow和fast同时一步一步走。fast到尾部时slow正好到达倒数第K-1个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
public class ListNode {
    int val;
    ListNode next = null;
  
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(head==null || k==0)return null;
        ListNode fast=head;
        for(int i=0;i<k-1;i++){
            ////防止K无效
            if(fast.next!=null){
                fast=fast.next;   
            }else{
                return null;
            }
              
        }
        ListNode slow=head;
        while(fast.next!=null){
            slow=slow.next;
            fast=fast.next;
        }
        return slow;
  
    }
}