LeetCode删除链表的倒数第N个节点——C

比眉伴天荒 2021-10-30 07:44 222阅读 0赞

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

## 题目描述 ##

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：
    给定一个链表: 1->2->3->4->5, 和 n = 2.
    当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：  
给定的 n 保证是有效的。

## 题解 ##

我想出来两种解法  
**1、暴力破解**  
n 代表倒数几个，那我们就计算出是第几个，顺序遍历出长度，然后删除指定位置即可。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    	struct ListNode* pTemp = (struct ListNode*)malloc(sizeof(struct ListNode));		//定义两个节点 
    	struct ListNode* pNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    	int m = 0;
    	pTemp = head;																	//指向头指针 
    	int i;
    	while (pTemp != NULL) {															//计算链表的长度
    		m++;
    		pTemp = pTemp->next;
    	}
    	i = m - n + 1;																	//计算删除哪个节点 
    	if (i == 1) {																	//如果是头
    		pTemp = head;
    		head = head->next;
    		free(pTemp);
    		pTemp = NULL;
    	}
    	else {																			//如果不是头
    		pTemp = head;
    		for (int j = 1; j < i - 1; j++) {
    			pTemp = pTemp->next;
    		}
    		pNode = pTemp->next;
    		pTemp->next = pTemp->next->next;											//删除指定节点 
    		free(pNode);
    		pNode = NULL;
    	}
    	return head;
    }

**2、双节点求解**  
因为是求倒数几个，我们可以设定一个节点为最后一个，距离最后一个节点为 n 的节点就是要删除的节点。

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    	int i;
    	struct ListNode* first = NULL;					//定义两个节点 
    	struct ListNode* second = NULL;
    	first = head;									//指向头结点 
    	second = head;
    
    	for (i = 0; i < n; i++) {						//倒数几个，即离最后一个间隔 
    		if (first != NULL) {						//退出条件 
    			first = first->next;
    		}
    		else {
    			return head;
    		}
    	}
    
    	if (first == NULL) {
    		return head->next;
    	}
    
    	while (first->next != NULL) {					//第一个节点后面为空说明这就是最后一个节点 
    		first = first->next;
    		second = second->next;
    	}
    	second->next = (second->next)->next;			//删除节点，第二个节点的后一个 
    
    	return head;
    }

## 调试 ##

#include<stdio.h>
    #include<malloc.h>
    
    struct ListNode {
    	int val;
    	struct ListNode* next;
    };
    
    //创建链表
    void CreateList(struct ListNode*& head, int length) {
    	struct ListNode* s, * r;
    	r = head;
    	for (int i = 1; i <= length; i++) {
    		s = (struct ListNode*)malloc(sizeof(struct ListNode));
    		s->val = i;
    		r->next = s;
    		r = s;
    	}
    	r->next = NULL;
    }
    
    int main() {
    	struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    	CreateList(head, 5);
    	head = head->next;
    	//	while(head!=NULL){
    	//		printf("%d ",head->val);
    	//		head=head->next;
    	//	}
    	struct ListNode* res = removeNthFromEnd(head, 2);
    	while (res != NULL) {
    		printf("%d ", res->val);
    		res = res->next;
    	}
    	return 0;
    }

## 结果 ##

![在这里插入图片描述][20190821180244540.png]**1、暴力破解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

**2、双节点求解**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[20190821180244540.png]: /images/20211029/205ee4c6e8f04ac2a05f49001e011a9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211029/a347ff8f1ed64a988cdacb1e8523e78e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211029/3ea2a0da0320475dbe0f2181739dca81.png