remove-nth-node-from-end-of-list

题目描述

对于给定的链表，删除倒数第n个节点，返回头节点。

解题思路

一个指针遍历两次，或者两个指针遍历一次。对于两个指针p,q，需要固定间隔长度n (p-q=n)，然后同时移动两个指针，直至q移到链表尾。此时q指向需要被移除的节点。注意返回空指针的处理。

易错情况：

([1,2],1) ([1,2],2) ([1],1)

编译时报错：error: expected unqualified-id before 'while'

原因是在类的定义中误写了循环体。

代码

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };	

ListNode * removeNthFromEnd(ListNode* head, int n) {
	ListNode *p =head, *q = head;
	int i = n;
    bool flag=false;
	while (i--)
	{
        if(q->next)
		    q = q->next;
        else
            flag=true;
	}
	if (!q->next&&flag)//要删除的是头节点
		if (p->next)
			return p->next;
		else
			return NULL;
	while (q->next)
	{
		q = q->next;
		p = p->next;
	}
	p->next = p->next->next;
	return head;
}