19.删除链表的倒数第N个结点.md

19. 删除链表的倒数第 N 个结点

url

题目

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

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

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
输入：head = [1], n = 1
输出：[]
输入：head = [1,2], n = 1
输出：[1]

方法

code

js

let removeNthFromEnd = (head, n) => {
  let fast = head;
  while (n-- > 0) {
      fast = fast.next;
  }
  if (fast === null)
      return head.next;
  let slow = head;
  while (fast.next !== null) {
      fast = fast.next;
      slow = slow.next;
  }
  slow.next = slow.next.next;
  return head;
};

go

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	fast := head
	for n > 0 {
		n--
		fast = fast.Next
	}
	if fast == nil {
		return head.Next
	}
	slow := head
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return head
}

java

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while (n-- > 0) {
            fast = fast.next;
        }
        if (fast == null) return head.next;
        ListNode slow = head;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}