题目详情

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

题目要求输入一个linked list 和一个数字n。要求我们返回删掉了倒数第n个节点的链表。

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.

想法

• 求倒数第n个节点，我们将这个问题转化一下。
• 我们声明两个指针low和fast，让fast和low指向的节点距离差保持为n。
• 这样当fast指向了链表中的最后一个节点时，low指针指向的节点就是我们所求的倒数第n个节点了。

解法

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode start = new ListNode(0);
        
        ListNode slow = start , fast = start;
        slow.next = head;
        
        //使fast点和slow点的差距为n
        for(int i=1;i<=n+1;i++){
            fast = fast.next;
        }
        
        //同时移动fast和slow 使得fast到达listnode的末尾
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        
        //删除倒数第n个节点
        slow.next = slow.next.next;      
        
        return start.next;
    }