Daily LeetCode 19. Remove Nth Node From End of List

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Medium

问题描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

思路及代码

这一题要删除链表的倒数第n个元素，我们可以先将链表反转，然后转化为删除第n个节点的问题，最后返回再次反转的链表即可。

代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        def reverseList(head):
            if head is None or head.next is None:
                return head;
            pre = None;
            cur = head;
            h = head;
            while cur:
                h = cur;
                tmp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = tmp;
            return h
        length = 0
        tmp = head
        while tmp:
            length += 1
            tmp = tmp.next
        if n == 1:
            return reverseList(reverseList(head).next)
        if length == n:
            return head.next
        head = reverseList(head)
        count = 1
        tmp = head
        while count != n - 1:
            count += 1
            tmp = tmp.next
        tmp.next = tmp.next.next

        return reverseList(head)

题目中的进阶要求是，在一次遍历过程中解决这个问题，我们可以设置两个指针，先让前指针走n步，走n步后，后指针也开始走，当前指针走到链表表尾时，后指针恰好走到要删除的元素的位置，这样就能够在一次遍历过程中得到结果。

代码如下：

def removeNthFromEnd(head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        #前后指针
        frontNode = head
        behindNode = head
        length = 0
        
        #前指针先走n步
        for i in range(n):
            frontNode = frontNode.next
            length += 1
        print "length = ",length
        print "n = ",n
        
        #代表要删除的是第一个元素
        if frontNode == None:
            return head.next
        
        #前后指针同时走
        while (frontNode.next):
            frontNode = frontNode.next
            behindNode = behindNode.next
            length += 1
        
        print "length = ",length
        
        #删除元素
        behindNode.next = behindNode.next.next
        return head