Remove Nth Node From End of List @LeetCode

 
package Level2;  
  
import Utility.ListNode;  
  
/** 
 *  
 * Remove Nth Node From End of List  
 *  
 * 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. 
 */  
public class S19 {  
  
    public static void main(String[] args) {  
        ListNode head = new ListNode(1);  
        ListNode l2 = new ListNode(2);  
        ListNode l3 = new ListNode(3);  
        ListNode l4 = new ListNode(4);  
        ListNode l5 = new ListNode(5);  
        head.next = l2;  
        l2.next = l3;  
        l3.next = l4;  
        l4.next = l5;  
          
        ListNode h = removeNthFromEnd(head, 5);  
        h.print();  
    }  
      
    public static ListNode removeNthFromEnd(ListNode head, int n) {  
        if(n == 0 || head == null){  
            return head;  
        }  
        if(n == 1 && head.next==null){  
            return null;  
        }  
          
        ListNode p = head, q = head;  
        // 让p先行q n个位置  
        for(int i=0; i<n; i++){  
            if(p != null){  
                p = p.next;  
            }else{  
                return head;  
            }  
        }  
          
        // 如果这个时候p已经是null，则说明删除的必定为head  
        if(p == null){  
            head = head.next;  
            return head;  
        }  
          
        // p和q一起前进  
        while(p.next != null){  
            q = q.next;  
            p = p.next;  
        }  
        // 删除元素  
        q.next = q.next.next;  
        return head;  
    }  
  
}  

补充：软件开发 , Java ,

上一个：Valid Parentheses @LeetCode
下一个：Palindrome Number @LeetCode