C语言链表基本操作

1. 
2. #include <stdio.h>
3. #include <stdlib.h>
4. 
5. typedef struct Node{
6.  int data;           //数据域
7.  struct Node *next;    //指针域
8. }Node;
9. 
10. 
11. Node* createList()
12. {
13.     Node* headNode= (Node *)malloc(sizeof(Node));
14.   headNode->next = NULL;
15. return headNode;
16. }
17. 
18. //创建节点
19. Node* createNode(int data)
20. {
21.   Node* newNode = (Node *)malloc(sizeof(Node)); //headNode成为了结构体变量
22.   newNode->data = data;
23.   newNode->next = NULL;
24.   return newNode;
25. }
26. 
27. 
28. 
29. //打印链表
30. void printList(Node* headNode)
31. {
32.   Node* pMove = headNode->next;
33.   while (pMove)
34.   {
35.     printf("%d\t", pMove->data);
36.     pMove = pMove->next;
37.   }
38.   printf("\n");
39. }
40. 
41. //头插节点，参数：插入那个节点，插入节点的数据是多少
42. void PushFront(Node* headNode, int data)
43. {
44.   //1创建插入的节点
45.   Node *newNode = createNode(data);
46.   newNode->next = headNode->next;
47.   headNode->next = newNode;
48. }
49. 
50. //从头部删除节点
51. void PopFront(Node* headNode)
52. {
53.   Node* pDel = headNode->next;
54.   headNode->next = headNode->next->next;
55.   free(pDel);
56. }
57. 
58. //尾插节点
59. void PushBack(Node* headNode, int data)
60. {
61.   Node* newNode = createNode(data);
62. 
63.   while (headNode->next)
64.     headNode = headNode->next;
65. 
66.   headNode->next = newNode;
67. }
68. 
69. //尾删节点
70. /*
71. 考虑三种情况
72. 链表为空时，直接返回
73. 链表中只有一个节点时，将headNode指向NULL
74. 链表中有多个节点时，遍历一遍链表，找到最后一个节点，并保存最后一个节点前一个节点的信息
75. */
76. void PopBack(Node *headNode)
77. {
78.   if (NULL == headNode)
79.   {
80.     return;
81.   }
82.   else if (NULL == headNode->next)
83.   {
84.     //free(headNode->next);
85.     headNode = NULL;
86.   }
87.   else
88.   {
89.     Node *pCur = headNode->next;
90.     Node *prev = headNode;
91.     while (pCur->next != NULL)
92.     {
93.       prev = pCur;
94.       pCur = pCur->next;
95.     }
96.     free(pCur);
97.     prev->next = NULL;
98.   }
99. }
100. 
101. //链表的删除：指定位置删除
102. void deleteNode(Node* headNode, int posData)
103. {
104.  Node* p = headNode->next;
105.  Node* pPre = headNode;
106.  if (p == NULL)
107.    printf("链表为空，无法删除\n");
108.  else
109.  {
110.    while (p->data != posData)
111.    {
112.      pPre = p;
113.      p = p->next;
114.      if (p == NULL)
115.      {
116.        printf("没有找到相关信息，无法删除\n");
117.        return;
118.      }
119.    }
120.    pPre->next = p->next;
121.    free(p);
122.  }
123. }
124. 
125. //反转链表
126. Node* reverseList(struct Node* headNode)
127. {
128.  if ((headNode == NULL) || (headNode->next == NULL))
129.    return headNode;
130.  else
131.  {
132.    Node* newHead = reverseList(headNode->next);
133.    headNode->next->next = headNode;
134.    headNode->next = NULL;
135.    return newHead;
136.  }
137. }
138. 
139. //删除链表的倒数第n个节点
140. Node* removeNthFromEnd(Node* headNode, int n) 
141. {
142.  //如果链表结点个数为0，直接返回 
143.  if (n == 0){
144.    return headNode;
145.  }
146. 
147.  //fastp为快指针，slowp为慢指针（用于指向待删除结点），slowp指向待删除结点的前驱结点。 
148.  Node *fastp = NULL, *slowp = NULL, *slowq = NULL;
149.  //先让快指针后跑n个结点 
150.  for (fastp = headNode; n>0; fastp = fastp->next, n--);
151.  slowp = headNode;
152.  //然后让快指针和慢指针一起向后跑，slowp为slowq的联动指针
153.  //当快指针跑到NULL时停止，这时候快指针一定指向待删除结点 
154.  while (fastp){
155.    slowq = slowp;
156.    slowp = slowp->next;
157.    fastp = fastp->next;
158.  }
159.  //如果要删除的结点为头结点，需要单独处理。否则，利用slowq->next=slowp->next即可删除结点 
160.  if (slowp == headNode){
161.    headNode = headNode->next;
162.  }
163.  else{
164.    slowq->next = slowp->next;
165.    free(slowp);
166.  }
167.  return headNode;
168. }
169. 
170. int main(void)
171. {
172.     Node* list = createList();
173. 
174.  PushFront(list, 1);
175.  PushFront(list, 2);
176.  PushFront(list, 3);
177.  PushFront(list, 4);
178.  PushFront(list, 5);
179.  printList(list);
180. 
181.  deleteNode(list, 3);
182. 
183.  //removeNthFromEnd(list, 2);
184.  printList(list);
185. 
186.  system("pause");
187.  return 0;
188. }