作者: turbo时间限制: 1S章节: DS:数组和链表
题目描述：
可使用以下代码，完成其中的removeNth函数，其中形参head指向无头结点单链表，n为要删除的结点序号，函数返回新链表的头指针。
#include<iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode() : val(0), next(NULL) {}
ListNode(int x) : val(x), next(NULL) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* removeNth(ListNode* head, int n) {
//填充本函数完成功能
}
};
ListNode *createByTail()
{
ListNode *head;
ListNode *p1,*p2;
int n=0,num;
int len;
cin>>len;
head=NULL;
while(n<len && cin>>num)
{
p1=new ListNode(num);
n=n+1;
if(n==1)
head=p1;
else
p2->next=p1;
p2=p1;
}
return head;
}
void displayLink(ListNode *head)
{
ListNode *p;
p=head;
cout<<"head-->";
while(p!= NULL)
{
cout<<p->val<<"-->";
p=p->next;
}
cout<<"tail\n";
}
int main()
{
ListNode* head = createByTail();
int n;
cin>>n;
head=Solution().removeNth(head,n);
displayLink(head);
return 0;
}
输入范例 :
5
1 2 3 4 5
2
输出范例：
head-->1-->3-->5-->tail
我的题解：
1 //数据结构：DHUOJ 删除链表的顺数及倒数第N个节点
2 #include<iostream>
3 using namespace std;
4 struct ListNode
5 {
6
7 int val;
8
9 ListNode* next;
10
11 ListNode() : val(0), next(NULL) {}
12
13 ListNode(int x) : val(x), next(NULL) {}
14
15 ListNode(int x, ListNode* next) : val(x), next(next) {}
16
17 };
18 class Solution {
19
20 public:
21
22 ListNode* removeNth(ListNode* head, int n) {
23
24 //特殊情况
25 if (!head)//头结点是空的 就不用删除 直接返回空
26 {
27 return head;
28 }
29 if (!head->next && n == 1) //两个结点的情况2 : 1 2 删除1 2 直接返回空
30 return NULL;
31 ListNode* xinhead = new ListNode;
32
33 xinhead->next = head;//给首元结点定义一个头结点
34 ListNode* p = xinhead, * q = xinhead;
35 ListNode* p_pre = xinhead, * q_pre = xinhead;
36
37 //p遍历到n pre是p的前驱结点
38 for (int i = 0; i < n; i++) {
39 p_pre = p;
40 p = p->next;
41 }
42 ListNode* p1 = p;
43
44 while (p1)//关键点 p到结尾的距离 等于q从首元结点出发到目的地的距离
45 {
46 q_pre = q;
47 q = q->next;
48 p1 = p1->next;
49 }
50
51 if (p == q)//指向头一个地方
52 {
53 p_pre->next = p->next;
54 }
55 else if (p != q && p->next != q && q->next != p)//p和q不相邻
56 {
57 p_pre->next = p->next;
58 q_pre->next = q->next;
59 }
60 else if (p->next == q)//相邻的话特判
61 {
62 p_pre->next = q->next;
63 }
64 else if (q->next == p)
65 {
66 q_pre->next = p->next;
67 }
68 ListNode* ans = xinhead->next;
69 return ans;
70 }
71
72 };
73 ListNode* createByTail()
74
75 {
76
77 ListNode* head;
78
79 ListNode* p1, * p2=NULL;
80
81 int n = 0, num;
82
83 int len;
84
85 cin >> len;
86
87 head = NULL;
88
89 while (n<len && cin >> num)
90
91 {
92
93 p1 = new ListNode(num);
94
95 n = n + 1;
96
97 if (n == 1)
98
99 head = p1;
100
101 else
102
103 p2->next = p1;
104
105 p2 = p1;
106
107 }
108
109 return head;
110
111 }
112 void displayLink(ListNode* head)
113
114 {
115
116 ListNode* p;
117
118 p = head;
119
120 cout << "head-->";
121
122 while (p != NULL)
123
124 {
125
126 cout << p->val << "-->";
127
128 p = p->next;
129
130 }
131
132 cout << "tail\n";
133
134 }
135 int main()
136
137 {
138
139 ListNode* head = createByTail();
140
141 int n;
142
143 cin >> n;
144
145 head = Solution().removeNth(head, n);
146
147 displayLink(head);
148
149 return 0;
150
151 }
