# 引言

题目链接:https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

# 题目大意

给定一个链表和数字 n, 删除链表倒数第 n 个节点并返回结果链表

Hint: Given n will always be valid.

  • 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 步后,快慢指针再同时前行。这样当先行指针走到链表末尾,后续指针正好可以操作倒数第 n 个节点,直接就地删除即可

# 复杂度

时间复杂度 O(n)

空间复杂度 O(1)

# AC 代码

c++ 版本

class Solution
{
  public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        if (nullptr == head)
        {
            return nullptr;
        }
        ListNode *ret = new ListNode();
        ret->next = head;
        ListNode *pre = ret;
        ListNode *cur = ret;
        while (n > 0 && nullptr != pre->next)
        {
            pre = pre->next;
            --n;
        }
        while (nullptr != pre->next)
        {
            pre = pre->next;
            cur = cur->next;
        }
        pre = cur->next;
        cur->next = cur->next->next;
        delete (pre);
        return ret->next;
    }
};

go 版本

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	if nil == head {
		return nil
	}
	ret := &ListNode{0, nil}
	ret.Next = head
	pre, cur := ret, ret
	for n > 0 && nil != pre.Next {
		pre = pre.Next
		n--
	}
	for nil != pre.Next {
		pre = pre.Next
		cur = cur.Next
	}
	pre = cur.Next
	cur.Next = cur.Next.Next
	return ret.Next
}
更新于 阅读次数