lc.删除链表倒数第n个节点
给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例 1：
1
2
|
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]
|
示例 2：
1
2
|
输入：head = [1], n = 1
输出：[]
|
示例 3：
1
2
|
输入：head = [1,2], n = 1
输出：[1]
|
提示：
链表中结点的数目为 sz
1
2
3
|
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
|
进阶：能尝试使用一趟扫描实现吗？
注意：本题与主站 19 题相同：
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
#define Node ListNode
void printNode(Node*x) {
while(x) {
printf("Node{%d}-> ",x->val);
x = x->next;
}
}
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
return rev(ok(rev(head),n));
}
Node* ok(Node* head,int n) {
if(n<0) return head;
if(n==0) return head;
//if n==1;
if(n==1) {
Node*temp = head->next;
//head = head->next
return temp;
}
Node *p = head;
for(int i=1;i<=n;i++) {
if(p==NULL) return head;
// 比如 i==2, p=node[2] , 删除前一个
if(i==n-1) {
Node* pre = p;
Node* target = p->next;
// printf("cur %d\n",p->val);
if(target) pre->next = target->next;
return head;
}
p = p->next;
}
return head;
}
Node* rev(Node*p) {
if(p==NULL) return NULL;
if(p->next == NULL) return p;
Node*pre = NULL,*cur = p;
p = NULL;
while(cur)
{
Node*temp = cur->next;
cur ->next = pre;
pre = cur;
cur = temp;
}
return pre;
}
};
|
