《Cracking the Coding Inteview》——第2章：链表——题目3

 1 // 2.2 Remove a node from middle of a linked list
 2 #include <cstdio>
 3 using namespace std;
 4 
 5 struct ListNode {
 6     int val;
 7     struct ListNode *next;
 8     ListNode(int x): val(x), next(nullptr) {};
 9 };
10 
11 class Solution {
12 public:
13     void deleteThatNode(ListNode *ptr) {
14         if (ptr != nullptr && ptr->next != nullptr) {
15             struct ListNode *tmp = ptr->next;
16             ptr->val = tmp->val;
17             ptr->next = tmp->next;
18             delete tmp;
19         }
20     }
21 };
22 
23 int main()
24 {
25     int i;
26     int n, k;
27     int val;
28     struct ListNode *head, *ptr;
29     Solution sol;
30     
31     while (scanf("%d", &n) == 1 && n > 0) {
32         // create a linked list
33         ptr = head = nullptr;
34         for (i = 0; i < n; ++i) {
35             scanf("%d", &val);
36             if (head == nullptr) {
37                 head = ptr = new ListNode(val);
38             } else {
39                 ptr->next = new ListNode(val);
40                 ptr = ptr->next;
41             }
42         }
43         
44         // remove a node from middle of the list
45         scanf("%d", &k);
46         k = k < 1 ? 1 : k;
47         k = k > n ? n : k;
48         ptr = head;
49         for (i = 1; i < k; ++i) {
50             ptr = ptr->next;
51         }
52         sol.deleteThatNode(ptr);
53         
54         // print the list
55         printf("%d", head->val);
56         ptr = head->next;
57         while (ptr != nullptr) {
58             printf("->%d", ptr->val);
59             ptr = ptr->next;
60         }
61         printf("\n");
62         
63         // delete the list
64         while (head != nullptr) {
65             ptr = head->next;
66             delete head;
67             head = ptr;
68         }
69     }
70     
71     return 0;
72 }