文章 224
评论 6
浏览 200768
LinkedList - 19. Remove Nth Node From End of List

LinkedList - 19. Remove Nth Node From End of List

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.

Follow up:

Could you do this in one pass?

思路:

删除链表倒数第n个节点,就是要走到倒数第n+1个节点进行操作,如果一次遍历解决问题,就得使用两个指针,两个指针开始都在同一个位置,然后fast指针先走n+1步,然后slow指针开始和fast指针一起走,这样fast指针走到链表尾部的时候,slow指针刚好走到链表倒数n+1个节点位置。然后删除第n个节点就好了。

代码:

java:

/**

 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy, fast = dummy;
        
        for (int i = 0; i < n + 1; i++) fast = fast.next;
        
        for(;fast != null;) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

标题:LinkedList - 19. Remove Nth Node From End of List
作者:michael
地址:https://www.bitbo-liuyang.com/articles/2019/07/28/1564321458988.html

Nothing just happens, it's all part of a plan.

取消