【题目】
分别实现两个函数，一个可以删除单链表中倒数第K个节点，另一个可以删除双链表中倒数第K个节点。
【要求】
如果链表长度为N，时间复杂度达到O（N），额外空间复杂度达到O（1）。
【题解】
从头遍历链表，每移动一次，K--，直至移动到链表尾部，此时
k>0,说明k太大，链表不用删除
k==0，链表长度即是k， 删除头结点即可
k<0,再次重头遍历链表，每移动一次，k++,
当k==0时，此时结点为要删除结点的前结点，使其指向下一个结点即可
双向链表一样，只不过需要注意前结点就好
1 #include 2 using namespace std; 3 4 struct SNode 5 { 6 int val; 7 SNode* next; 8 SNode(int a = 0) :val(a), next(nullptr) {} 9 }; 10 11 struct DNode 12 { 13 int val; 14 DNode* pre; 15 DNode* next; 16 DNode(int a = 0) :val(a), pre(nullptr), next(nullptr) {} 17 }; 18 19 template 20 void printList(T head) 21 { 22 T p = head->next; 23 while (p) 24 { 25 cout << p->val << "->"; 26 p = p->next; 27 } 28 cout << endl; 29 } 30 31 SNode* DeleteSList(SNode* head, int k) 32 { 33 SNode*p = head->next; 34 while (p) 35 { 36 --k; 37 p = p->next; 38 } 39 if (k > 0)//k大于链表的长度，不用删除 40 return head; 41 else if (k == 0)//k==链表的长度，删除头结点即可 42 return head->next; 43 p = head; 44 while (k != 0)//找到删除结点的前结点 45 { 46 ++k; 47 p = p->next; 48 } 49 p->next = p->next->next; 50 return head; 51 } 52 53 DNode* DeleteDList(DNode* head, int k) 54 { 55 DNode*p = head->next; 56 while (p) 57 { 58 --k; 59 p = p->next; 60 } 61 if (k > 0)//k大于链表的长度，不用删除 62 return head; 63 else if (k == 0)//k==链表的长度，删除头结点即可 64 return head->next; 65 p = head; 66 while (k != 0)//找到删除结点的前结点 67 { 68 ++k; 69 p = p->next; 70 } 71 p->next->next->pre = p; 72 p->next = p->next->next; 73 return head; 74 } 75 76 77 int main() 78 { 79 SNode* head1 = new SNode(); 80 DNode* head2 = new DNode(); 81 SNode* p1 = head1; 82 DNode* p2 = head2; 83 for (int i = 1; i < 10; ++i) 84 { 85 SNode* q1 = new SNode(i); 86 DNode* q2 = new DNode(i); 87 p1->next = q1; 88 p1 = q1; 89 p2->next = q2; 90 q2->pre = p2; 91 p2 = q2; 92 } 93 cout << "删除前：" << endl; 94 printList(head1); 95 printList(head2); 96 97 head1 = DeleteSList(head1, 4); 98 head2 = DeleteDList(head2, 4); 99 cout << "删除后：" << endl;100 printList(head1);101 printList(head2);102 103 return 0;104 }