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;
  
     }
}