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

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

leetcode 链接

思路：

1. 使用 dummy 节点存储头节点，然后遍历链表.

2. 先让快指针走 n 步，然后快慢指针一起走，当快指针走到链表尾部时，慢指针刚好走到倒数第 n 个节点的前一个节点。

3. 然后将慢指针的 next 指向下一个节点的 next，最后返回 dummy.next 即可。

typescript 解法

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;

  while (n > 0) {
    fast = fast.next;
    n--;
  }

  while (fast != null && fast.next != null) {
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next;

  return dummy.next;
}

go 解法

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
    dummy := &ListNode{
        Next: head,
    }
    fast, slow := dummy, dummy
    for n > 0 {
        fast = fast.Next
        n --
    }
    for fast != nil && fast.Next != nil {
        fast = fast.Next
        slow = slow.Next
    }

    slow.Next = slow.Next.Next
    return dummy.Next

}