【说明】:
本文是左程云老师所著的《程序员面试代码指南》第二章中“在单链表和双链表中删除倒数第K个节点”这一题目的C++复现。
本文只包含问题描述、C++代码的实现以及简单的思路,不包含解析说明,具体的问题解析请参考原书。
感谢左程云老师的支持。
【题目】:
分别实现两个函数,一个可以删除单链表中倒数第 K 个节点,另一个可以删除双链表中倒数第 K 个节点。
【要求】:
如果链表长度为 N,时间复杂度达到 O(N),额外空间复杂度达到 O(1)。
【思路】:
在确定待删除节点的位置有一个小技巧,大家可以看代码推断,也可以翻看左老师的原书奥。
【编译环境】:
CentOS6.7(x86_64)
gcc 4.4.7
【实现】:
实现及测试代码:
1 /*
2 *文件名:lists_delLastKth.cpp
3 *作者:
4 *摘要:删除单链表或双链表的倒数第 K 个节点
5 */
6
7 #include <iostream>
8
9 using namespace std;
10
11 struct SingleNode
12 {
13 int value;
14 SingleNode *next;
15 };
16
17 struct DoubleNode
18 {
19 int value;
20 DoubleNode *pre;
21 DoubleNode *next;
22 };
23
24 SingleNode* removeLastKthNode(SingleNode *head,int lastKth)
25 {
26 if(NULL == head || 1 > lastKth)
27 return head;
28 SingleNode *cur = head;
29 while( NULL != cur)
30 {
31 lastKth--;
32 cur = cur->next;
33 }
34 if(0 == lastKth)
35 {
36 cur = head;
37 head = head->next;
38 delete cur;
39 }
40 if(0 > lastKth)
41 {
42 cur = head;
43 while(++lastKth != 0)
44 cur = cur->next;
45 SingleNode *tmp = cur->next;
46 cur->next = tmp->next;
47 delete tmp;
48 }
49 return head;
50 }
51
52 DoubleNode* removeLastKthNode(DoubleNode *head,int lastKth)
53 {
54 if(NULL == head || 1 > lastKth)
55 return head;
56 DoubleNode *cur = head;
57 while( NULL != cur)
58 {
59 lastKth--;
60 cur = cur->next;
61 }
62 if(0 == lastKth)
63 {
64 cur = head;
65 head = head->next;
66 head->pre = NULL;
67 delete cur;
68 }
69 if(0 > lastKth)
70 {
71 cur = head;
72 while(++lastKth != 0)
73 cur = cur->next;
74 DoubleNode *tmp = cur->next;
75 cur->next = tmp->next;
76 if(NULL != tmp->next)
77 tmp->next->pre = cur;
78 delete tmp;
79 }
80 return head;
81 }
82
83 int main()
84 {
85 SingleNode *shead = NULL;
86 SingleNode *sptr;
87 DoubleNode *dhead = NULL;
88 DoubleNode *dptr;
89 for(int i =0;i<10;i++)
90 {
91 if(NULL == shead && NULL == dhead)
92 {
93 //单链表
94 shead = new SingleNode;
95 shead->value = i;
96 shead->next = NULL;
97 sptr = shead;
98 //双链表
99 dhead = new DoubleNode;
100 dhead->value = i;
101 dhead->next = NULL;
102 dhead->pre = NULL;
103 dptr = dhead;
104 continue;
105 }
106 //单链表
107 sptr->next = new SingleNode;
108 sptr = sptr->next;
109 sptr->value = i;
110 sptr->next = NULL;
111 //双链表
112 dptr->next = new DoubleNode;
113 dptr->next->pre = dptr;
114 dptr = dptr->next;
115 dptr->value = i;
116 dptr->next = NULL;
117 }
118 int k = 5;
119 cout << "Single linked list before remove last " << k << "th data: " << endl;
120 sptr = shead;
121 while(NULL != sptr)
122 {
123 cout << sptr->value << " ";
124 sptr = sptr->next;
125 }
126 cout << endl;
127 cout << "Double linked list before remove last " << k << "th data: " << endl;
128 dptr = dhead;
129 while(NULL != dptr)
130 {
131 cout << dptr->value << " ";
132 dptr = dptr->next;
133 }
134 cout << endl;
135
136 removeLastKthNode(shead,k);
137 removeLastKthNode(dhead,k);
138
139 sptr = shead;
140 dptr = dhead;
141 cout << "Single linked list after removed: " << endl;
142 while(NULL != sptr)
143 {
144 cout << sptr->value << " ";
145 sptr = sptr->next;
146 }
147 cout << endl;
148 cout << "Double linked list after removed: " << endl;
149 while(NULL != dptr)
150 {
151 cout << dptr->value << " ";
152 dptr = dptr->next;
153 }
154 cout << endl;
155 return 0;
156 }
View Code
【说明】:
这个算法不难,我写的测试代码(main 函数)较为麻烦,大家理解哈。
注:
转载请注明出处;
转载请注明源思路来自于左程云老师的《程序员代码面试指南》。
原文链接: https://www.cnblogs.com/PrimeLife/p/5353874.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/231472
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!