leetcode：Remove Nth Node From End of List （移除从尾部数的第N个节点）

Question：

Given a linked list, remove the n^th 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.

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/

Note:
Given n will always be valid.
Try to do this in one pass.

给定一个链表，如上边数据结构所示，删除倒数第N个节点。

算法思想：① 没有想起十分高效的方法，但是时间复杂度仍然是O（n），就是先要遍历整个链表，看有几个节点，比如有n1个。

② 假如要删除倒数n个节点，然后对链表遍历到第n1-n的位置，执行删除操作，要特别注意的是如果要删除的元素是链表的第一个元素该单独处理。

代码设计：

 1 class Solution{
 2     public ListNode removeNthFromEnd(ListNode head, int n) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         int temp=count(head)-n;
 5         if(0==temp)
 6             return head.next; //如果要删除第一个节点
 7         ListNode h=new ListNode(-1); //临时节点用来当首地址，记录head指向的位置
 8         h.next=head;
 9         ListNode p=h;
10         for(int i=0;i<temp;i++)//找到要删除节点的前一个位置
11             p=p.next;
12         ListNode del=p.next; //删除节点
13         p.next=del.next;
14         del=null;  //释放要删除节点的内存空间
15         p=h.next;  
16         h=null;        //释放临时节点的内存空间
17         return p;
18     }
19     public int count(ListNode l1){  //计算链表节点数
20         int i=0;
21         while(l1!=null){
22             i++;
23             l1=l1.next;
24         }
25         //System.out.println(i);
26         return i;
27     }
28 }

2013-10-24 01:57:13