首页 > 代码库 > [leetcode]Remove Nth Node From End of List

[leetcode]Remove Nth Node From End of List

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.

算法:删除单链表的节点一定要找到其前驱节点。

 

思路1:先求出list的长度,从而在遍历的时候可以计数,通过计数从而找到其前驱节点,空间时间复杂度都是O(n),但是两次遍历,计算list长度的时候,第二遍遍历的时候。

比较简单,不再实现了。

思路2,双指针,让第二个指针先走n步,然后齐步走,第二个指针走到底的时候,第一个指针刚好停在其前驱,一次遍历

代码如下:

 1 public class Solution { 2     public ListNode removeNthFromEnd(ListNode head, int n) { 3         ListNode hhead = new ListNode(0); 4         hhead.next = head; 5         ListNode one = hhead; 6         ListNode two = hhead; 7         for(int i = 0; i < n; two = two.next,i++); 8         while(two.next != null){ 9             one = one.next;10             two = two.next;11         }12         one.next = one.next.next;13         return hhead.next;14     }15 }

链表题,双指针真的很常用,甚至是三指针,这道题是很经典的面试题,只不过本题把难度限制了,比如n的大小范围合法,默认list合法等