【LeetCode】（No.019）删除链表的倒数第N个节点

PM小王

发布于 2019-07-02 16:21:25

3590

发布于 2019-07-02 16:21:25

NO.19 删除链表的倒数第N个节点

一、写在前面

刷题模块的初衷是恶补数据结构和算法，不管自己的公众号怎样变化，刷题这个模块一定会保留下去，期待自己能成为offer收割机。LeetCode 第十八题传输门：【LeetCode】（No.018）四数之和天给大家分享的是LeetCode 第十九题：删除链表的倒数第N个节点。

前十题汇总：【LeetCode】打卡记录（NO.1-10）为面试而生，期待你的加入。

二、今日题目

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

示例：

给定一个链表: 
1->2->3->4->5,和 n = 2.当删除了倒数第二个节点后，链表变为
 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

三、分析

这个题目的大意就是删除一个单链表中的倒数第N个结点，这个题目还是比较简单的下面是具体的解题思路。

两次遍历单链表，首先获得单链表中的结点个数count，然后从前往后找到第count-N+1个结点，即我们要删除的结点，删除即可。一次遍历链表，用两个指针p,q分别指向头结点，然后先将其中一个指针p向后移动N个位置，再将p,q同时往后移动，当指针p移动到末尾时，q指针指向的结点即为我们要删除的结点。

四、解题

第一种解题：

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.next = None
 6
 7class Solution:
 8    def removeNthFromEnd(self, head, n):
 9        temp = head
10        count = 0
11        while temp!=None:
12            temp = temp.next
13            count += 1
14        temp = head
15        index = 0
16        if count==n:
17            return head.next
18        else:
19            while index!=(count-n-1):
20                temp = temp.next
21                index += 1
22            temp.next = temp.next.next
23            return head

第二种解题：

 1# Definition for singly-linked list.
 2# class ListNode:
 3#     def __init__(self, x):
 4#         self.val = x
 5#         self.next = None
 6
 7class Solution:
 8    def removeNthFromEnd(self, head, n):
 9        p = head
10        q = head
11        index = 0
12        while index!= n:
13            p = p.next
14            index += 1 
15        if p==None:
16            return head.next
17        while p.next!= None:
18            p = p.next
19            q = q.next
20        q.next = q.next.next
21        return head

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2018-11-22，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员小王微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度