Remove-Nth-Node-From-End-of-List(two points)

传送门

题意:

给你一个链表,删除链表的倒数第n个结点。(要求只遍历一次链表)

思路:

如果可以遍历链表两次,那就很简单了 第一遍确立链表的长度$L$,然后删除倒数倒数第n个等价于删除第$L-n+1$个结点。

只遍历一次链表,我们可以使用双指针first和second,然后始终维护first和second的之间的gap为$n+1$ ,当first指向None时,那么second指向的下一个结点就是要删除的结点。

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Definition for singly-linked list.

# class ListNode:

# def __init__(self, x):

# self.val = x

# self.next = None



class Solution:

def removeNthFromEnd(self, head, n):

root = ListNode(0)

root.next = head

first = root

second = root

gap = 0

while first != None:

while gap <= n and first != None:

first = first.next

gap += 1

if first != None:

second = second.next

first = first.next

second.next = second.next.next

return root.next


-------------本文结束感谢您的阅读-------------


本文标题:Remove-Nth-Node-From-End-of-List(two points)

文章作者:Statusrank

CSDN博客欢迎来访!

发布时间:2019年04月19日 - 09:04

最后更新:2019年04月19日 - 09:04

原始链接:https://statusrank.xyz/articles/3946e2a4.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

万水千山总是情,就给五毛行不行!