链表 | RAMSEY

单链表，头结点不存数据域。

想在链表中找到它的第i个结点，只能从头结点开始，沿着指向下一个节点的指针遍历链表，它的时间效率是 $O(n)$ 。而在数组中，可以根据下标在 $O(1)$ 时间内找到第i个元素。

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

#include "stdafx.h"

#include "iostream"

using namespace std;

class Node{

int data;

Node *next;

public:

Node();

Node(const int &inputdata);

void InserAfter(Node * p);

Node *RemoveAfter();

Node *MoveNext(Node *p);

int GetValue(Node *p);

friend class List;//以List为友元类，List可直接访问Node的私有成员，与结构一样方便

};

Node::Node(){

next = NULL; //此结点的数据域不用，仅作头结点

}

Node::Node(const int &inputdata){

data = inputdata;

next = NULL; //设置当前结点

}

//在当前结点后插入一个结点

void Node::InserAfter(Node *p){

p->next = next;

next = p;

}

//返回需要删除的那个结点，真正删除需要delete，然后把next指针指向这个删除结点的后一结点

Node* Node::RemoveAfter(){

Node *tempP = next;

if (next == NULL) tempP = NULL;//已到尾结点，后面无结点

else next = tempP->next;

return tempP;

}

int Node::GetValue(Node *p){

return p->data;

}

Node *Node::MoveNext(Node *p){

return p->next;

}

class List{

Node *head, *tail;

public:

List();

~List();

void MakeEmpty();

void PrintList();

Node * Find(int finddata);//搜索数据域与data相同的结点，返回该结点的位置

Node *Gethead();

int Length();

void InsertFront(Node *p);//向前生成链表，在表头插入一个结点

void InsertRear(Node *p);//向后生成链表，在表尾添加一个结点

void InsertOrder(Node *p);//按升序生成链表

void ConnectListNode(Node* pCurrent, Node* pNext);

Node *CreatNode(int inputdata);

Node *DeleteNode(Node *p);//删除指定结点

Node *KthNodefromEnd(Node *head, int k);

Node *MedianNode(Node *phead, int n);

int IsLoopList(Node* pHead); //判断是否存在环

int IsLoopList1(Node* pHead); //判断是否存在环

void PrintListReverse(Node*pHeadNext);

Node* multiply(Node* phead, char* pStr1, char* pStr2);

};

List::List(){

head = tail = new Node();

}

List::~List(){

MakeEmpty();

delete head;

}

void List::MakeEmpty(){

Node *tempP;

while (head->next!=NULL){

tempP = head->next;

head->next = tempP->next;//使头结点后的第一个结点从链中脱离

delete tempP; //删除脱离下来的结点

}

tail = head; //表头指针与表尾指针均指向表头指针，表示空链

}

Node * List::Find(int finddata){

Node *tempP = head->next;

while (tempP != NULL&&tempP->data != finddata) tempP = tempP->next;

return tempP;

//显然如果成功返回结点地址，如果不成功则返回尾结点的指针域，NULL，这里已经包含了搜索尾结点

}

//第一个结点的地址可以通过表头指针head找到

int List::Length(){

Node*tempP = head->next;

int count = 0;

while (tempP != NULL){

tempP = tempP->next;

count++;

}

return count;

}

Node* List::Gethead(){

return head;

}

void List::InsertFront(Node *p){

p->next = head->next;

head->next =p ;

if (tail == head) tail = p;

}

void List::InsertRear(Node *p){

p->next = tail->next;//把p的next指针域置为Null

tail->next = p; //把原来tail的指针域链到p

tail = p; //把p作为现在的tail

}

Node*List::CreatNode(int inputdata){

Node* tempP = new Node(inputdata);

return tempP;

}

Node*List::DeleteNode(Node *p){

Node *tempP = head;

while (tempP->next != NULL&&tempP->next != p) tempP = tempP->next;

if (tempP->next == tail) tail = tempP;

return tempP->RemoveAfter();

}

void List::PrintList(){

Node *tempP = head->next;

while (tempP != NULL){

cout << tempP->data << '\t';

tempP = tempP->next;

}

cout <<"null"<< endl;

}

Node *List::KthNodefromEnd(Node *phead, int k){

if (phead == NULL || k ==0)

return NULL;

Node *p = phead;

Node *q = phead;

int j = 0;

while (p != NULL){

if (j <= k){

j++; //执行了k+1次

p = p->next;

}

else{

p = p->next;

q = q->next;

}

return q;

}

Node * List::MedianNode(Node *phead,int n){

if (phead == NULL )

return NULL;

Node *pNode = phead;

Node *qMidNode = phead;//尾指针的next为NULL

while (pNode->next != NULL&&pNode->next->next != NULL){

pNode = pNode->next->next;

qMidNode = qMidNode->next;//返回的是中间结点的前一个，如果链表长度为偶数

}

if (n % 2 == 0){

return qMidNode;

}

else

return qMidNode->next;

}

void List::ConnectListNode(Node* pCurrent, Node* pNext){

if (pCurrent == NULL){

cout << "前一个结点不能为空" << endl;

}

else{

pCurrent->next = pNext;

}

int List::IsLoopList(Node* pHead)

{

if (pHead == NULL)

return NULL;

Node* pFast = pHead;//第一个指针，步长为2

Node* pSlow = pHead;//第二个指针，步长为1

while (pFast != NULL&&pFast->next!= NULL&&pSlow!=NULL){

pSlow = pSlow->next;

if (pFast->next != NULL)

pFast = pFast->next->next;

if (pSlow == pFast)

return 1;

}

return -1;

}

int List::IsLoopList1(Node* pHead)

{

Node *pCur1 = pHead;//定义结点pCur1

int pos1 = 0;

while (pCur1->next != NULL) //pCur1结点存在

{

Node *pCur2 = pHead;

int pos2 = 0;

pos1++;

while (pCur2->next != NULL)

{

pos2++; //pCur2步数自增

if (pCur1 == pCur2)

{

if (pos1 == pos2)//说明还没有环

break;

else

return 1;

}

pCur2 = pCur2->next;

}

pCur1 = pCur1->next;

}

return -1;

}

int _tmain(int argc, _TCHAR* argv[])

{

Node *P1;

List list1, list2;//构造函数中已生成表头指针

//list1.PrintList();

int a[11] = { 2, 4, 5, 6, 7, 9, 10, 20, 21, 22, 23 };

//int i, j;

for (int i = 0; i < 11; i++){

P1 = list1.CreatNode(a[i]);

list1.InsertFront(P1);//向前生成链表算法

P1 = list2.CreatNode(a[i]);

list2.InsertRear(P1);//向后生成链表算法

}

cout << "Print list1:" << endl;

list1.PrintList();

cout << "Print list2:" << endl;

list2.PrintList();

int k;

int n = list1.Length();

cout << "The length of the list(n) is: " << n<<endl;

cout << "Which one to select form tail(Not greater than n-1):";

cin >> k;

Node *phead = list1.Gethead();

list1.ConnectListNode(list1.Find(2), list1.Find(7));

int islooplis = list1.IsLoopList1(phead);

Node *q = list1.KthNodefromEnd(phead,k);

//Node *p = list1.Gethead();

//Node *q = list1.Gethead();

//int j = 0;

//while (p != NULL){

// if (j <= k){

// j++;

// //if (p->MoveNext(p) != NULL)

// p = p->MoveNext(p);

// //else

// // cout << "Arrive at the tail of the list" << endl;

// }

// else{

// p = p->MoveNext(p);

// q = q->MoveNext(q);

// }

//}

Node *qMidNode = list1.MedianNode(phead,n);

cout << "The last k node's value is: " << q->GetValue(q) << endl;

cout << "The median node's value is: " << qMidNode->GetValue(qMidNode) << endl;

list1.DeleteNode(q);

cout << "Print list1 after delete the last kth node:" << endl;

list1.PrintList();

system("pause");

return 0;

}

QQ截图20150525140602

list1：向前生成算法；list2：向后生成算法。

相关试题：

1、输入一个单向链表，输出该链表中倒数第k个结点

自然可以想到，先走到链表的尾端，再从尾端回溯k步。可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我们的思路。
假设整个链表有n个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点（从0开始计数）。计算链表的长度n，只要从头结点开始往后走n-k-1步就可以了。

时间复杂度是O(n)，但需要遍历链表两次。第一次得到链表中结点个数n，第二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。

上述存在缺点：如果输入的链表的结点个数很多，有可能不能一次性把整个链表都从硬盘读入物理内存，那么遍历两遍意味着一个结点需要两次从硬盘读入到物理内存。

能不能把链表遍历的次数减少到1？

解决方法：在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前，第二个指针保持不动；在第k+1步开始，第二个指针也开始从链表的头指针开始遍历。由于两个指针的距离保持在k+1，当第一个（前面的）指针到达链表的尾结点时，第二个指针（后面的）指针正好是倒数第k个结点（尾结点为倒数第0个结点）。

注意：想好边界条件再开始编写代码，再者要在编写完代码之后再用边界值、边界值减1、边界值加1都运行一次。

在写代码的时候需要考虑鲁棒性，最好采用防御性编程，就是考虑在哪些地方会出错，然后提前加上错误判断，这样避免因此错误输入而导致程序崩溃。

输入的pListHead为空指针，由于代码会尝试访问空指针指向的内存，程序崩溃
输入的以pListHead为头结点的链表的结点少于k，又会出现尝试访问空指针指向的内存。
输入的参数k小于等于0。根据题意k的最小值应为1。

2、删除单链表倒数第K个节点（思路和第一题一样，找到倒数第k个结点）

删除一个结点的实现：

Node*List::DeleteNode(Node *p){

Node *tempP = head;

while (tempP->next != NULL&&tempP->next != p) tempP = tempP->next;

//找到后继结点为p，

if (tempPnext== tail) tail = tempP;

return tempP->RemoveAfter();

}

//删除当前结点的后继结点，返回该结点

Node* Node::RemoveAfter(){

Node *tempP = next;//指向所要删除的结点

if (next ==NULL) tempP = NULL;

else next = tempP->next;

//将当前结点的next指针指向删除结点后一个结点

return tempP;

}

3、输入一个单向链表。如果该链表的结点数为奇数，输出中间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。

为了解决这个问题，可以定义两个指针，同时从链表的头结点出发，一个指针一次走一步，另一个指针一次走两步。当走得快的指针走到链表的末尾时，走得慢的指针正好在链表的中间。

在单向链表中，每个结点都包含一个指向下一个结点的指针，最后一个结点的这个指针被设置为空。但如果把最后一个结点的指针指向链表中存在的某个结点，就会形成一个环，在顺序遍历链表的时候，程序就会陷入死循环。我们的问题就是，如何检测一个链表中是否有环，如果检测到环，如何确定环的入口点（即求出环长，环前面的链长）。

解法1：从头开始遍历链表，把每次访问到的结点（或其地址）存入一个集合（hashset）或字典（dictionary），如果发现某个结点已经被访问过了，就表示这个链表存在环，并且这个结点就是环的入口点。这需要O(N)空间和O(N)时间，其中N是链表中结点的数目。

解法2：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了6步，此时若q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。

解法3：O(1)空间、O(N)时间

准备两个指针，同时从链表头出发，一个每次往前走一步，另一个每次往前走两步。如果链表没有环，那么经过一段时间，第二个（速度较快的）指针就会到达终点；但如果链表中有环，两个指针就会在环里转圈，并会在某个时刻相遇。

int List::IsLoopList(Node* pHead){

if (pHead == NULL)

return NULL;

Node* pFast = pHead;//第一个指针，步长为2

Node* pSlow = pHead;//第二个指针，步长为1

while (pFast != NULL&&pFast->next!= NULL&&pSlow!=NULL){

pSlow = pSlow->next;

if (pFast->next != NULL)

pFast = pFast->next->next;

if (pSlow == pFast)

return 1;

}

return -1;

}

链表形状类似数字 6 。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...

1 2	当 i＜a 时，S(i)=i ；当 i≥a 时，S(i)=a+(i-a)%b 。

带环的链表

分析追赶过程:
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另外，碰撞时必须在环内，不可能在甩尾段，有 x>=a 。

连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。

根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。同为前进 a 步，同为连接点，所以必然发生碰撞。

综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。

假设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为t，环的长度为r，慢指针总共走了s步，则快指针走了2s步。另外，快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离)，得到以下关系：
   s = a + t;
   2s = a + nr + t;
   =>a + t= nr;
   =>a = nr - t;

分别从碰撞点、头指针开始走，相遇的那个点就是连接点

4、反转单链表
思路一、新建一个链表，可以采用向后生成链表算法或者向前生成链表算法。

定义3个指针，分别指向当前遍历到的结点、它的前一个结点及后一个结点。

Node* List::ReverseList(Node* pHead){

Node* pReversedHead = NULL;//反转后的头结点即尾结点, 其pNext=NULL

//如果输入链表头指针为NULL,返回NULL

Node* pNode = pHead;

Node *pPrev = NULL;

while (pNode != NULL)

{

Node *pNext = pNode->next;//后一个结点

pNode->next = pPrev;

if (pNext == NULL) //到达尾结点

pReversedHead = pNode;//翻转后链表的头结点是原先的尾结点

pPrev = pNode;

pNode = pNext;

}

return pReversedHead;

}

2）用递归实现反转链表？

5、从尾到头打印链表

通常打印只是一个只读操作，不能改变链表的结构。

遍历的顺序是从头到尾，可输出的顺序却是从尾到头。“先进后出”，这是一种栈的思想。

void List::PrintListReverse(){

stack<Node*> nodes;

Node*pNode=head->next;

while(pNode!=NULL){

nodes.push(pNode);

pNode=pNode->next;

}

while(!nodes.empty()){

pNode=nodes.top();

cout<<pNode->data<<'\t';

nodes.pop();

}

cout <<"null"<< endl;

}

Node *phead = list1.Gethead();

list1.PrintListReverse_Recursive(phead);

递归在本质上就是一个栈结构！！！先递归输出它后面的结点，然后再输出该结点自身。

void List::PrintListReverse_Recursive(Node*phead){

Node *p = phead;

if(p!=NULL){

if(p->next!=NULL){

PrintListReverse_Recursive(p->next);

}

cout<<p->data<<'\t';

}

Node *phead = list1.Gethead();

Node *pnext=phead11->MoveNext(phead);

list1.PrintListReverse_Recursive(pnext);

有个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。

6、合并两个排序的链表（要求合并后仍旧是递增排序）

Node* List::ListMerge(Node*phead1,Node*phead2){

if(phead1==NULL)

return phead2;

else if(phead2==NULL)

return phead1;

Node *pMergeHead=NULL;

if(phead1->data>phead2->data){

pMergeHead=phead2;

pMergeHead->next=ListMerge(phead1,phead2->next);

}

else{

pMergeHead=phead1;

pMergeHead->next=ListMerge(phead1->next,phead2);

}

return pMergeHead;

}

7、大数相乘

#define toInt(a) (*(a)-'0')

//暂时不考虑字符串的有效性

Node*List::multiply(Node*pHead, char*str1, char*str2) {

int len1;

int len2;

int i;

int j;

int carry; //进位标志

Node* pNode = pHead;

Node* pTemp;

len1 = strlen(str1);

len2 = strlen(str2);

//首先每位相乘，不考虑进位

for (i = len1 - 1; i >= 0; i--){

pNode = pHead;

//找到指针前一个位置

for (j = 1; j < len1 - i; j++){

pNode = pNode->next;

}

for (j = len2 - 1; j >= 0; j--)

{

if (NULL == pNode->next)

{

pTemp = (Node*)malloc(sizeof(Node));

if (NULL == pTemp)

{

return NULL;

}

pTemp->next = NULL;

pTemp->data= 0;

pNode->next = pTemp;

}

pNode = pNode->next;

pNode->data+= toInt(str1 + i)*toInt(str2 + j);

}

//循环进位

pNode = pHead;

carry = 0;

while (NULL != pNode->next)

{

pNode = pNode->next;

pNode->data+= carry; //先考虑前一次进位

carry = pNode->data / 10; //再设置下一次进位

pNode->data %= 10; //最后赋余10之后的值

}

//处理最后一次进位

if (0 != carry)

{

pTemp = (Node*)malloc(sizeof(Node));

if (NULL == pTemp)

{

return NULL;

}

pTemp->next = NULL;

pTemp->data = carry;

pNode->next = pTemp;

}

return pHead;

}

List list1, list2;//构造函数中已生成表头指针

//list1.PrintList();

Node *phead = list1.Gethead();

Node* pMulti=list1.multiply(phead,"135","234");

list1.PrintListReverse(phead->MoveNext(phead));