leetcode 19. Remove Nth Node From End of List

2017-08-16

题意

删掉链表元素，按尾巴节点倒数第几来删，给定一个倒序的顺序n，删除倒数n的数字。

我的思路

这种题，一般思路都是遍历一遍链表，然后找到那个倒数位。删除它。时间复杂度为O(2L-n),L为链表的长度。

如何做到O(L)?

如下图所示

新建一个节点，两个指针指向它，它的next就是head，让其中一个指针先行n+1步，这样两个指针之间会相差n个元素，然后两个指针一起遍历，直到先行的指针到了null，这个时候前一个指针就在倒数第n的位置的前一个位置。删掉它即可。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode node = new ListNode(0);
        node.next = head;
        ListNode slow = node;
        ListNode fast = node;
        for(int i=0;i<n+1;i++)
            fast = fast.next;
        while(fast!=null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return node.next;
    }
}

注意一个地方：有人可能这么写

ListNode slow = new ListNode(0);
slow.next = head;
ListNode fast = slow;
...
return head;

这么写会遇到一个坑，比如删掉的就是head节点时就会出错。