LeetCode19-删除链表的倒数第N个节点
昨天,从澳洲回来放暑假的好哥们来这儿找我了,真的是把大半个学校走遍了,晚上Jio酸的不行。不过他带来的巧克力是真的好吃,是不是国外的巧克力都好吃啊!最后再吐槽一下,
昨天晚上一屁股把我的公交卡给碾成了两节,陪伴了我四年的公交卡啊!你命不该绝,怪就怪你的主人长了块大屁股
19. 删除链表的倒数第N个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
思路
我们注意到这个问题可以容易地简化成另一个问题:删除从列表开头数起的第 (L - n + 1)(L−n+1) 个结点,其中 LL 是列表的长度。只要我们找到列表的长度 LL,这个问题就很容易解决。
代码如下:
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
length = self.getLength(head)
if n > length:
return
dump = ListNode(0)
dump.next = head
dump_copy = dump
delete_index = length - n
while delete_index > 0:
delete_index -= 1
dump_copy = dump_copy.next
dump_copy.next = dump_copy.next.next
return dump.next
# 获取head指针的长度
def getLength(self, head):
length = 0
head_copy = head
while head_copy:
length += 1
head_copy = head_copy.next
return length
if __name__ == '__main__':
list_node = [1, 2, 3, 4, 5]
l1 = ListNode(0)
cur_l1 = l1
for index in range(len(list_node)):
cur_l1.next = ListNode(list_node[index])
cur_l1 = cur_l1.next
n = 2
result = Solution().removeNthFromEnd(l1.next, n)
while result:
print(result.val)
result = result.next
执行效率一般般,在30%左右
这两天做到后面的23题——合并k个有序链表时(不小心暴露了进度)受到了一些启发,其实我们可以用一个数组把链表中每个节点的值给保存起来,链表的pop()方法很容易删除倒数第N个节点的值,最后再用个链表把处理过的数组中的值导进来就行了,是不是觉得很有意思!
代码如下:
class Solution:
def removeNthFromEnd(self, head, n):
"""
:type head: ListNode
:type n: int
:rtype: ListNode
"""
head_list = []
head_copy = head
while head_copy:
head_list.append(head_copy.val)
head_copy = head_copy.next
if len(head_list) < n:
return
head_list.pop(len(head_list)-n)
Head = ListNode(0)
head_copy = Head
for index in head_list:
head_copy.next = ListNode(index)
head_copy = head_copy.next
return Head.next
if __name__ == '__main__':
list_node = [1, 2, 3, 4, 5]
l1 = ListNode(0)
cur_l1 = l1
for index in range(len(list_node)):
cur_l1.next = ListNode(list_node[index])
cur_l1 = cur_l1.next
n = 2
result = Solution().removeNthFromEnd(l1.next, n)
while result:
print(result.val)
result = result.next
执行效率是不错的,我测得几次都在52s