0019. Remove Nth Node From End of List

19. Remove Nth Node From End of List #

题目 #

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

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.

题目大意 #

删除链表中倒数第 n 个结点。

解题思路 #

这道题比较简单,先循环一次拿到链表的总长度,然后循环到要删除的结点的前一个结点开始删除操作。需要注意的一个特例是,有可能要删除头结点,要单独处理。

这道题有一种特别简单的解法。设置 2 个指针,一个指针距离前一个指针 n 个距离。同时移动 2 个指针,2 个指针都移动相同的距离。当一个指针移动到了终点,那么前一个指针就是倒数第 n 个节点了。

代码 #


package leetcode

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 解法一
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	var fast, slow *ListNode
	fast = head
	slow = head
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	if fast == nil {
		head = head.Next
		return head
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return head
}

// 解法二
func removeNthFromEnd1(head *ListNode, n int) *ListNode {
	if head == nil {
		return nil
	}
	if n <= 0 {
		return head
	}
	current := head
	len := 0
	for current != nil {
		len++
		current = current.Next
	}
	if n > len {
		return head
	}
	if n == len {
		current := head
		head = head.Next
		current.Next = nil
		return head
	}
	current = head
	i := 0
	for current != nil {
		if i == len-n-1 {
			deleteNode := current.Next
			current.Next = current.Next.Next
			deleteNode.Next = nil
			break
		}
		i++
		current = current.Next
	}
	return head
}



⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者