19.remove Nth Node From End of List

Published 2018-08-01 22:53:23

Leetcode地址

Github地址

题干

Given a linked list, remove the n-th node from the end of list and return its head.

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

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

给定的 n 保证是有效的。

Follow up:

Could you do this in one pass?

你能尝试使用一趟扫描实现吗?

思路

  • 利用快慢指针,设置空链表的下一个节点为list

  • 第一个指针先走n步

  • 第一个指针走到最后,第二个指针跟着走

  • 第二个指针走到的位置就是要删除的位置

  • p.next=p.next.next

代码

type ListNode struct {
	Val  int
	Next *ListNode
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	p := &ListNode{}
	s := p
	e := p
	p.Next = head
	for i := 0; i <= n; i++ {
		s = s.Next
	}
	for s != nil {
		s = s.Next
		e = e.Next
	}
	e.Next = e.Next.Next
	return p.Next
}
comments powered by Disqus