吴良超的学习笔记

LeetCode 解题报告(19)--从后往前删除链表第n个元素

原题如下:

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个节点。一开始想到的方法就是先找出链表元素总数num,再删除第num-n+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
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""

nextNode = head.next
num = 1
while not nextNode == None:
num +=1
nextNode = nextNode.next

delete = num-n+1
if delete == 1:
return head.next

else:
currNode = head
i = 1
while i<delete-1:
currNode = currNode.next
i+=1
currNode.next = currNode.next.next
return head

这种方法虽然能AC,但是题目提示了Try to do this in one pass,也就是这道题目存在只需遍历一遍的解法。在网上查找后发现可以先让一个指针p1从head向后移动n个node,然后另外一个指针p2此时从head出发和p1一起移动,当p1移动到最后一个节点时,p2后面的一个元素即为需要删除的元素。实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""


p1=head
i = 1
while i<=n:
p1 = p1.next
i += 1
p2 = head
while not p1.next==None:
p1 = p1.next
p2 = p2.next
p2.next =p2.next.next
return head

但是在提交时出错,排查后发现上述代码删除的node刚好是head时会出错,因为是从1开始往后n步,当删除的node是head是,n是所有节点的数目,而此时会导致p1为None,然后p1.next自然会报错。

解决方法是增加一个无意义的node指向head,从这个node开始遍历即可。

实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""

dummy=ListNode(0)
dummy.next=head
p1=p2=dummy
for i in range(n):
p1=p1.next
while p1.next:
p1=p1.next
p2=p2.next
p2.next=p2.next.next
return dummy.next

除了上面的解决方法,一开始还想过通过将链表反转再删除第n个node即可,但是题目意思是删除这个node不能改变其他node原来的排序。虽然不符合题意,但是这里一并附上代码记录链表反转的一种方法:

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
class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""


preNode = head
nextNode = head.next
tmp = None
while not nextNode == None:
preNode.next = tmp
tmp = preNode
preNode = nextNode
nextNode = nextNode.next
preNode.next = tmp
head = preNode
if n==1:
return head.next
else:
i = 1
while i < n-1:
nextNode = nextNode.next
i += 1
nextNode.next = nextNode.next.next
return head