剑指Offer11 在O(1)内删除链表结点

  1 /*************************************************************************
  2     > File Name: 11_DeleteLinkNode.c
  3     > Author: Juntaran
  4     > Mail: JuntaranMail@gmail.com
  5     > Created Time: 2016年08月30日 星期二 02时10分27秒
  6  ************************************************************************/
  7 
  8 #include <stdio.h>
  9 #include <malloc.h>
 10 #include <string.h>
 11 
 12 // 链表结构体
 13 struct ListNode
 14 {
 15     int val;
 16     ListNode* next;
 17 };
 18 
 19 // 构造链表
 20 ListNode* createList()
 21 {
 22     struct ListNode* head;
 23     struct ListNode* p;
 24     struct ListNode* q;
 25     head = p = (ListNode*)malloc(sizeof(ListNode));
 26     head->val = 0;
 27     for (int i = 1; i <= 10; ++i)
 28     {
 29         q = (ListNode*)malloc(sizeof(ListNode));
 30         q->val = i;
 31         p->next = q;
 32         p = q;
 33     }
 34     p->next = NULL;
 35     return head;
 36 }
 37 
 38 // 顺序输出链表
 39 void PrintList(ListNode* head)
 40 {
 41     if (head == NULL)
 42         return;
 43     ListNode* temp = head;
 44     printf("PrintList:
");
 45     while (temp != NULL)
 46     {
 47         printf("%d ", temp->val);
 48         temp = temp->next;
 49     }
 50     printf("
");
 51 }
 52 
 53 // 删除结点
 54 void DeleteListNode(ListNode** head, ListNode* key)
 55 {
 56     if (head==NULL || key==NULL)
 57         return;
 58     
 59     // 如果要删除头结点
 60     if (*head == key)
 61     {
 62         *head = (*head)->next;
 63         free(key);
 64         key = NULL;
 65         return;
 66     }
 67     
 68     // 如果要删除尾结点
 69     if (key->next == NULL)
 70     {
 71         ListNode* temp = *head;
 72         while (temp->next != key)
 73             temp = temp->next;
 74         
 75         temp->next = NULL;
 76         free(key);
 77         key = NULL;
 78         return;
 79     }
 80     
 81     // 其他情况
 82     ListNode* temp = key->next;
 83     key->val = temp->val;
 84     key->next = temp->next;
 85     
 86     free(temp);
 87     temp = NULL;
 88     
 89 }
 90 
 91 
 92 int main()
 93 {
 94     ListNode* test = createList();
 95     PrintList(test);
 96     
 97     ListNode* key1 = test;                // 头结点测试
 98     ListNode* key2 = test->next->next;    // 正常情况测试
 99     ListNode* key3 = test;
100     while (key3->next)
101     {
102         key3 = key3->next;                // 尾结点测试
103     }
104     
105     printf("key1 is %d
", key1->val);
106     printf("key2 is %d
", key2->val);
107     printf("key3 is %d
", key3->val);
108     
109     DeleteListNode(&test, key1);
110     PrintList(test);
111     DeleteListNode(&test, key2);
112     PrintList(test);
113     DeleteListNode(&test, key3);
114     PrintList(test);
115     
116     return 0;
117 }