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