在单链表和双链表中删除倒数第K个节点

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“在单链表和双链表中删除倒数第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 函数）较为麻烦，大家理解哈。

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。