0019._remove_nth_node_from_end_of_list.md

Links:

1. https://leetcode.com/problems/remove-nth-node-from-end-of-list/
2. https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

Tags

1. 链表
2. 双指针

Solution 1 两次遍历

等价于另外一个问题：删除从列表开头数起的第 (L - n + 1)个结点，其中 L 是列表的长度。现在L是未知量。所以要两次遍历，第一次找出L，第二次找到L-n的节点，然后进行删除操作x.next = x.next.next.

哑结点dummy node 用来简化某些极端情况，例如列表中只含有一个结点，或需要删除列表的头部。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head

        p1 = head
        length = 0

        while p1:
            p1 = p1.next
            length += 1

        p1 = dummy
        length -= n
        while length > 0:
            p1 = p1.next
            length -= 1

        p1.next = p1.next.next
        
        return dummy.next

---

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getLength(head *ListNode) (length int) {
	current := head

	for current != nil {
		length++
		current = current.Next
	}

	return
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	length := getLength(head)
	dummy := &ListNode{Val: 0, Next: head}
	current := dummy

	for i := 0; i < length-n; i++ {
		current = current.Next
	}

	current.Next = current.Next.Next

	return dummy.Next
}

Solution2 一次遍历 快慢指针

快指针先走n + 1步，然后快慢指针一起走，直到走完链表。 这时候，慢指针所指的就是所删除节点的前一个节点。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = head
        
        fast = dummy
        slow = dummy

        for i in range(n + 1):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next

        return dummy.next

---

Go

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Val: 0, Next: head}

	fast, slow := dummy, dummy

	for i := 0; i < n+1; i++ {
		fast = fast.Next
	}

	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}

	slow.Next = slow.Next.Next

	return dummy.Next
}