删除链表的倒数第N个节点

题目

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

题解

思路1

dummyHead 和 双指针

fast 指针先走 n 步

接着 slow指针 和 fast指针一起走，直到fast指针走到最后

删除 slow指针所指节点

返回dummyHead.next , 不直接返回head ，因为可能删的就是head。

时间复杂度: O(N)- 空间复杂度: O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */


public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return head;

    ListNode dummy = new ListNode(-1);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    //fast 先走 n步
    for (int i = 0; i < n; i++) {
        fast = fast.next;
    }

    //slow 和 fast 一起走
    while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }

    //删除节点
    slow.next = slow.next.next;

    return dummy.next;
}

思路2

进阶：你能尝试使用一趟扫描实现吗？

在思路1的基础上用一个循环解决：

时间复杂度: O(N)- 空间复杂度: O(1)

public ListNode removeNthFromEnd(ListNode head, int n) {
    if (head == null)
        return head;

    ListNode dummy = new ListNode(-1);
    dummy.next = head;


    ListNode fast = dummy;
    ListNode slow = dummy;

    int count = 0;
    while (fast.next != null) {
        if (count < n) {
            count += 1;
            fast = fast.next;
        } else {
            slow = slow.next;
            fast = fast.next;
        }
    }

    //删除节点
    slow.next = slow.next.next;

    return dummy.next;
}