删除链表中倒数第n个节点

remove Nth node from end of list

描述：

　　给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。

样例：

　　给出链表1->2->3->4->5->null和 n = 2.

　　删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.

挑战：

　　O(n)时间复杂度

思路：

　　先求得链表长度，查询链表依次时间O(n)，第二次找到倒数n位置，删除之，时间共O(n)+O(n)~ O(n)

 1 """
 2 Definition of ListNode
 3 class ListNode(object):
 4 
 5     def __init__(self, val, next=None):
 6         self.val = val
 7         self.next = next
 8 """
 9 class Solution:
10     """
11     @param head: The first node of linked list.
12     @param n: An integer.
13     @return: The head of linked list.
14     """
15     def removeNthFromEnd(self, head, n):
16         # write your code here
17         dummy = ListNode(0)
18         dummy.next = head
19         
20         # for length
21         len = 0
22         pre = dummy
23         while pre.next:
24             len += 1
25             pre = pre.next
26             
27         # find the Nth node from end of list
28         cnt = 0 
29         tarCnt = len - n
30         pre = dummy
31         while pre.next:
32             if cnt == tarCnt:
33                 pre.next = pre.next.next
34                 break
35             else:
36                 cnt +=1
37                 pre = pre.next
38                 
39         return dummy.next

该博客停止更新，继续关注请移步: www.foolweel.com