[python 刷题] 19 Remove Nth Node From End of List
题目:
题目说的是就是移除倒数第 n 个结点,如官方给的案例:
这里提供的 n
就是 2,也就是倒数第二个结点
这道题本身的难度不是很大,最简单的方法就是 2-pass,第一个循环找到链表的长度,随后循环到 n - 2
的长度即可,这个解法代码如下:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l, t = 0, head
while t:
l += 1
t = t.next
prev, next = head, head.next
while l - n - 1 > 0 and next:
prev = prev.next
next = next.next
n += 1
if l == n:
return head.next
if not next:
prev.next = None
return head
prev.next = next.next
return head
这么处理一下,其实边界条件挺多的(主要是当 n = 0
和 n = len(linked list)
这两个情况)
不过这道题有个 follow up:Could you do this in one pass?
也就是问一个循环能不能解决问题
这也是一个可以用双指针解决的方法,题目中说 nth from the emd
,其实换个方式理解也可以理解成 nth from start
:
这个时候的 fast 指向 3,slow 则是指向新建的 head,这里的差是 n + 1
是因为差第 n
个值是被移除的
这个时候 slow
和 fast
同时进入循环,当 fast
指向空时,slow
也指向了 n - 1
个值:
代码如下:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return head
t = ListNode(0, head)
slow, fast = t, head
while n:
fast = fast.next
n -= 1
while fast:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return t.next
这里取 n = 1
反而是因为代码实现起来会方便一些,否则就要使用 while n - 1:
和 while fast.next:
结束循环:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
if not head:
return head
t = ListNode(0, head)
slow, fast = t, head
while n - 1:
fast = fast.next
n -= 1
while fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return t.next
这两个代码从结果上来说是一样的
整体上来说,链表也好、二分搜索也好,这些 +1
/-1
的边界条件其实就会影响代码会不会 AC