class Solution {
public:
int getLength(ListNode* head) {
int length = 0;
while (head) {
++length;
head = head->next;
}
return length;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
int length = getLength(head);
ListNode* cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur->next;
}
cur->next = cur->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
问:ListNode* dummy = new ListNode(0, head);这里的head既然指的是next,那为什么cur->next不是cur—>head。
问:ListNode* ans = dummy->next;为什么要单独设立一个ans指针,此时cur为什么不用呢,我觉得ans多余
问:dummy会随着cur = cur->next;的移动而移动吗,为什么
问:ListNode* ans = dummy->next;这一段有什么意义,他只是单纯指向链表中的一个点啊,他能代指能个修改后的链表吗,为什么
来个负责任的大佬
问:ListNode* dummy = new ListNode(0, head);这里的head既然指的是next,那为什么cur->next不是cur—>head。
一般写链表时候这么写比较方便,否则你处理头节点和处理中间节点要写俩套代码。因为头节点和中间节点不同,头节点之前没有东西,而中间节点之前还有节点。加上一个dummy,一套代码就够了,否则就要判断。这里也一样,如果我要删除第一个节点怎么办。就是n为链表长度的时候,你处理起来就麻烦了
问:ListNode* ans = dummy->next;为什么要单独设立一个ans指针,此时cur为什么不用呢,我觉得ans多余
同一
问:dummy会随着cur = cur->next;的移动而移动吗,为什么
不会,你改变的是cur ,就是说把cur指向了它的next
问:ListNode* ans = dummy->next;这一段有什么意义,他只是单纯指向链表中的一个点啊,他能代指能个修改后的链表吗,为什么
为什么有dummy,问一里给你解释了,dummy-〉next,其实就是head
ListNode* dummy = new ListNode(0, head);
这个ListNode相关的代码能不能贴出来一下?
ListNode *removeNthFromEnd(ListNode *head, int n)
{
// Assume 1: n starts from 0.
// Assume 2: This function deletes the n-th node from the end of the list,
// i.e. if n = 0, delete the last node; if n = 1, delete the node
// before the last one; ...; if n = length - 1, delete the head node.
// Assume 3: The return value of the function is the head of the new list,
// because the original head might be deleted.
int length = getLength(head);
assert(n >= 0 && n < length); // check n is valid
ListNode *prev = nullptr; // point to the previous node
ListNode *p = head; // point to current node
for (int i = 0; i < length - n - 1; i++)
{
prev = p;
p = p->next;
}
if (prev)
prev->next = p->next; // remove the node pointed by p from the list
else
head = p->next; // p points to the head, i.e. remove the head from the list. head is changed.
delete p; // delete the node pointed by p.
return head; // return the head of the new list.
}