【链表】删除链表中的结点

算法思路：

1. 因为我们只被给了要删除的结点，无法根据修改此结点之前的结点的指针域进行删除
2. 我们可以将下一个结点的值赋给此结点，然后删除下一结点

题解：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    node->val = node->next->val;
    node->next = node->next->next;
}

【链表】删除倒数结点

题目链接

做题时思路：

1. 先遍历一遍确定链表长度size
2. 用for循环遍历到size-n-1的位置，将指针p设位此位置的结点
3. 若n==size大小，则将头结点设为头结点指针域下一个结点。
4. 若n！= size则将p→next设为p→next→next

做题题解：(正确 非递归解决方法）

struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
    struct ListNode* p = head;
		//得到链表长度
    int size = getLength(head);
		//如果n的大小与链表长度相等，说明删除的时首元结点，需要特殊处理
		if(n == size){
			//将头结点变为头结点的下一个结点
			head = head->next;
			return head;
		}
		//我们通过for循环找到要删除结点之前的一个结点。size-n为要删除结点，size-n-1为删除结点之前的一个结点
    for(int i = 0;i < size-1-n;i++) {
        p=p->next;
    }
		//删除结点
    p->next = p->next->next;
    return head;
}

int getLength(struct ListNode* head) {
	struct ListNode* p = head;
	int size = 0;
	while(p) {
		size++;
		p = p->next;
	}
	return size;
}

解法2：双指针解法