设计网站大全网,做个小程序开发的公司,苏州市建设安全监督局网站,外贸黄页网站题目#xff1a;
给你一个链表#xff0c;删除链表的倒数第 n 个结点#xff0c;并且返回链表的头结点。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], n 2
输出#xff1a;[1,2,3,5]示例 2#xff1a;
输入#xff1a;head [1], n 1
输出#xff1a;…题目
给你一个链表删除链表的倒数第 n 个结点并且返回链表的头结点。 示例 1 输入head [1,2,3,4,5], n 2
输出[1,2,3,5]示例 2
输入head [1], n 1
输出[]示例 3
输入head [1,2], n 1
输出[1]
思路1暴力遍历
很简单的遍历完链表一边遍历一边计数n删除倒数第N个结点即删除正数第n-N1个结点。
代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
int getlen(struct ListNode* head){int lenth0;while(head){headhead-next;lenth;}return lenth;
}
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummymalloc(sizeof(struct ListNode));dummy-val0;dummy-nexthead;struct ListNode* curdummy;int lengetlen(head);for(int i0;ilen-n;i){curcur-next;}cur-nextcur-next-next;struct ListNode* ansdummy-next;free(dummy);return ans;
}
思路2递归
链表天生自带的递归性质在这个简单条件面前自然也可以使用在无法知道链表结点数的情况下我们就自然无法在递的上面做文章自然而然就只能在归的过程中进行计数归一次就计数N
代码实现
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {static int N;//这里比较特别的一点就是我们使用静态变量作用是在不同的归的栈中使得变量不改变while(!head){N0;return head;}head-nextremoveNthFromEnd(head-next, n);N;if(Nn){struct ListNode* tmphead-next;free(head);return tmp;}return head;
}
思路3双指针
第一个暴力遍历的效率不高的一大原因就是因为遍历的次数重复了一次增添一个指针自然可以渐少一次遍历利用前后指针的范围差准确的确定倒数第N个结点的所在处
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummymalloc(sizeof(struct ListNode));dummy-val0;dummy-nexthead;struct ListNode* predummy;struct ListNode* curdummy;for(int i0;in-1;i){curcur-next;}while(cur-next-next){prepre-next;curcur-next;}pre-nextpre-next-next;struct ListNode* tmpdummy-next;free(dummy);return tmp;
}
思路4栈
用栈来装下所有的结点再一步一步出栈。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct STACK{struct ListNode* val;struct STACK* next;};
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummymalloc(sizeof(struct ListNode));dummy-val0;dummy-nexthead;struct STACK* stkNULL;struct ListNode* curdummy;while(cur){struct STACK* tmpmalloc(sizeof(struct STACK));tmp-valcur;tmp-nextstk;stktmp;curcur-next;}for(int i0;in;i){struct STACK* tmpstk-next;free(stk);stktmp;}struct ListNode* prestk-val;pre-nextpre-next-next;struct ListNode* ansdummy-next;free(dummy);return ans;
}
