[Leetcode] Remove Nth Node From End of List 移除倒数第N的节点

java 3 2016-02-29 13:03
女装

Remove Nth Node From End of List

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

For 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. Try to do this
in one pass.

迭代法

复杂度

时间 O(N) 空间 O(1)

思路

典型的快慢指针。先用快指针向前走n步,这样快指针就领先慢指针n步了,然后快慢指针一起走,当快指针到尽头时,慢指针就是倒数第n个。不过如果要删除这个节点,我们要知道的是该节点的前面一个节点。另外,如果要删的是头节点,也比较难处理。这里使用一个dummy头节点,放在本来的head之前,这样我们的慢指针从dummy开始遍历,当快指针为空是,慢指针正好是倒数第n个的前一个节点。最后返回的时候,返回dummy的下一个。

注意

因为有可能删除头节点,我们需要一个dummyhead

代码

java

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // 快指针先走n步
        for(int i = 0; i < n; i++){
            fast = fast.next;
        }
        // 从dummy开始慢指针和快指针一起走
        ListNode curr = dummy;
        while(fast != null){
            fast = fast.next;
            curr = curr.next;
        }
        // 删除当前的下一个节点
        curr.next = curr.next.next;
        return dummy.next;
    }
}

python

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        fast = dummy
        for i in range(0, n):
            fast = fast.next
        slow = dummy
        while(fast.next is not None):
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next
女装
文章评论