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

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

思路

思路1:

• 先计算链表的长度

• 设置一个dummy节点，简化处理

• 先把pre指向dummy，然后走len-n步，找到需要移除节点的上一个节点

• 然后让pre节点指向下下个节点

• 最后返回dummy.next

思路2: 只需要遍历一次。

• 让first指向head，然后走n步

• 让second指向dummy

• 然后first和second一起走，直到first为空

• 再让second指向下下个节点

• 最后返回dummy.next

Code

代码1：

func removeNthFromEndV1(head *ListNode, n int) *ListNode {
	len := 0
	p := head
	for p != nil {
		len++
		p = p.Next
	}

	var dummy = &ListNode{Val: -1, Next: head}
	pre := dummy
	for i := 0; i < len-n; i++ {
		pre = pre.Next
	}

	pre.Next = pre.Next.Next
	return dummy.Next
}

代码2：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Val: -1, Next: head}
	first := head //注意此处为head
	second := dummy
	for i := 0; i < n; i++ {
		first = first.Next
	}

	for first != nil {
		first = first.Next
		second = second.Next
	}

	second.Next = second.Next.Next
	return dummy.Next
}