0%

Leetcode 019 Remove Nth Node From End of List

Posted on Edited on

题目要求：

输入链表的起始节点和整数n，需要去掉从链表结尾起第n个节点，然后返回新链表的起始节点。

思路：

用双指针方法确定位置，第一个指针先从头至尾移动n个节点，第二个指针开始移动，两个指针同步移动直至第一个指针到达链表尾部，第二个指针就到达了距离尾部距离n的节点，删除即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        placeHolder = ListNode(0)
        placeHolder.next = head
        p = q = placeHolder
        for i in range(n):
            p = p.next
        while p.next:
            p, q = p.next, q.next
        q.next = q.next.next
        return placeHolder.next