LeetCode 19. Remove Nth Node From End of List

发表于 | 分类于 |

19. Remove Nth Node From End of List

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

示例：

1
2
3
给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

思路

两次遍历

简单方案：第一次遍历确定链表长度l，第二次遍历找到l-n+1的点，并删掉该点。为了处理复杂情况，在头节点前加入一个空节点作为新的头节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0)
        dummy.next = head
        p = head
        q = dummy       # 空节点
        i =  0          # 链表长度      
        while p:
            i = i+1 
            p = p.next
        j = 0
        while j < i - n:
            j = j+1
            q = q.next
        q.next = q.next.next        
        return dummy.next

一次遍历

两个指针用来遍历，其中fast指针比slow快n。当fast指针达到最后一个的指针时，slow指针正好达到要删除的节点的前一个节点。整个过程一次遍历。
时间复杂度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        p = q = head
        i =  0
        while p:
            i = i+1
            p = p.next
        j = 1
        while j < i - n:
            j = j+1
            q = q.next
        q.next = q.next.next        
        return head

LeetCode代码和详细解题报告 Github地址：https://github.com/zhengjingwei/LeetCode