【LintCode 简单】174. 删除链表中倒数第n个节点

分手后的思念是犯贱 2022-11-28 13:32 130阅读 0赞

1.问题描述：

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

2.样例：

> Example 1:  
>     Input: list = 1->2->3->4->5->null， n = 2  
>     Output: 1->2->3->5->null
> 
>   
> Example 2:  
>     Input:  list = 5->4->3->2->1->null, n = 2  
>     Output: 5->4->3->1->null

3.代码：

"""
    Definition of ListNode
    class ListNode(object):
        def __init__(self, val, next=None):
            self.val = val
            self.next = next
    """
    
    
    class Solution:
        """
        @param head: The first node of linked list.
        @param n: An integer
        @return: The head of linked list.
        """
    
        def removeNthFromEnd(self, head, n):
            # write your code here
            l1 = head
            count = 1
            # 找到最后一个结点
            while l1.next is not None:
                l1 = l1.next
                count += 1
            # 计算应该删除的第几个结点
            delete = count - n + 1
            # 处理删除头结点的情况
            if delete == 1:
                return head.next
            # 删除非头结点的情况
            l1 = head
            l2 = head
            while delete:
                if delete == 1:
                    l1.next = l2.next
                else:
                    l1 = l2
                    l2 = l2.next
                delete -= 1
            # 最后返回head
            return head

思路是先遍历一遍链表计算出链表总共的结点数目，然后就能够知道需要删除的是正向中的第几个结点。然后使用两个指针去循环链表，当第一个指针达到需要删除的结点时，将第二个指针指向第一个指针的下一个结点，就可以完成删除。注意：对头结点删除需要进行特殊处理。