19. Remove Nth Node From End of List

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        
        ListNode start = new ListNode(0);
        ListNode slow = start,fast = start;//同时指向start,slow,fast操作的时候会影响到start
        start.next = head;//把头指向head
        /*
        * 先派fast先走两步,fast在这里只是充当探底,找到倒数第二个数的作用
        * */
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        /*
        * 一起走两步
        * */
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        /*
        * 关键的操作,跳过slow后面的那个
        * */
        slow.next = slow.next.next;//但是为什么要设置一个头呢,是不是因为怕影响原始的你的node呢
        return start.next;
    }
}

按照python版本的写的,说实话,觉得没必要加上虚拟第一个节点,加上第一个节点可以避免第一个head的node造成的逻辑错误,下面的方法就是不需要的:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp=head,pre=head;
        while(n--!=0){
            tmp=tmp.next;
        }
        
        if(tmp==null) return head.next;//list contains n ele
        
        while(tmp.next!=null){
            pre=pre.next;
            tmp=tmp.next;
        }
        pre.next=pre.next.next;
        
        return head;
    }

这一种的方法的话需要额外加一个判断,判断是不是删除第一个节点