数据结构与算法-单链表

链表

参考学习：B站-逊哥带你学编程

单链表

单链表-存储结构

typedef int ElemType;typedef struct node{ElemType data;struct node *next;
}Node;

单链表-初始化

Node *initList()
{Node *head = (Node *)malloc(sizeof(Node));head->data = 0;head->next = NULL;return head;
}

单链表-头插法

int insertHead(Node *L, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); //分配内存p->data = e;  //赋值p->next = L->next; //插入的节点指向向头节点指向的节点L->next = p; //头节点指向新节点
}

图示：

单链表-遍历

void listNode(Node *L) //传入头节点
{Node *p = L->next; //指向第一个节点 有数据的节点while(p != NULL)  //若不为空{printf("%d ", p->data); //输出节点的值p = p->next;    //指向下一个节点}printf("\n");   //换行
}

单链表-尾插法

Node *get_tail(Node *L)
{Node *p = L;while(p->next != NULL) //找到最后一个节点{p = p->next; //指向下一个节点}return p; //返回最后一个节点
}Node* insertTail(Node *tail, ElemType e)
{Node *p = (Node *)malloc(sizeof(Node)); //分配内存p->data = e; //赋值tail->next = p; //最后一个节点指向新节点p->next = NULL; //新节点指向空return p; //返回新节点
}

图示：

单链表-在指定位置插入数据

//插入节点
int insertNode(Node *L, int pos, ElemType e)
{Node *p = L;//用于保存要插入的位置的前一个节点int i = 0;while(i < pos-1) //找到要插入的位置{p = p->next; //指向下一个节点i++;if (p == NULL) //若为空{printf("Position is invalid\n"); //位置无效return 0;}Node *q = (Node *)malloc(sizeof(Node)); //分配内存q->data = e; //赋值q->next = p->next; //新节点指向下一个节点p->next = q; //前一个节点指向新节点return 1;
}

图示：

单链表-删除节点

找到要删除节点的前置节点p

用指针q记录要删除的节点

通过改变p的后继节点实现删除

释放删除节点的空间

图示：

int deleteNode(Node *L, int pos, ElemType *e)
{Node *p = L; //用于保存要删除的位置的前一个节点int i = 0;while(i < pos-1) //找到要删除的位置{p = p->next; //指向下一个节点i++;if (p == NULL) //若为空{printf("Position is invalid\n"); //位置无效return 0;}Node *q = p->next; //要删除的节点*e = q->data; //保存删除的节点的值p->next = q->next; //前一个节点指向下一个节点free(q); //释放内存return 1;}
}

单链表-获取链表长度

int listLength(Node *L)
{Node *p = L->next; //指向第一个节点int length = 0;while(p != NULL) //若不为空{length++; //长度加1p = p->next; //指向下一个节点}return length;
}

单链表-释放链表

指针 p指向头节点后的第一个节点
判断指针 p 是否指向空节点
如果 p不为空，用指针 q记录指针p的后继节点。
释放指针 p 指向的节点
指针 p和指针 q指向同一个节点，循环上面的操作。

图示：

int freeList(Node *L)
{Node *p = L->next; //指向第一个节点Node *q;while(p != NULL) //若不为空{q = p->next; //保存下一个节点free(p); //释放内存p = q; //指向下一个节点}L->next = NULL; //头节点指向空return 1;
}

单链表-应用

问题1：

解决方案：

使用双指针（快慢指针）

代码实现：

//链表应用快慢指针
int findNodeFS(Node *L, int k)
{Node *fast = L->next; //快指针Node *slow = L->next; //慢指针for (int i = 0; i < k; i++){fast = fast->next; //快指针先走k步}while (fast != NULL) //快指针不为空{fast = fast->next; //快指针走一步slow = slow->next; //慢指针走一步}printf("倒数第%d的节点的值：%d\n", k, slow->data); //输出慢指针的值return slow->data; //返回慢指针的值
}

问题2：

解决方案：

快慢指针。

第一步：先求出两个链表的长度m和n。

第二步：Fast指针指向较长的链表，先走m-n步或n-m步。

第三步：同步移动指针，判断它们是否指向同一个节点

代码实现：

Node* findIntersectionNode(Node *headA, Node *headB)
{if(headA == NULL || headB == NULL) //若有一个为空{return NULL; //返回空}Node *p = headA; //指向第一个链表int lenA = 0;int lenB = 0;//计算链表A的长度while(p != NULL) //若不为空{lenA++; //长度加1p = p->next; //指向下一个节点}p = headB; //指向第二个链表while (p != NULL) //若不为空{lenB++; //长度加1p = p->next; //指向下一个节点}Node *fast;Node *slow;int step;if(lenA > lenB) //若A的长度大于B的长度{fast = headA; //快指针指向Aslow = headB; //慢指针指向Bstep = lenA - lenB; //步数为A的长度减去B的长度}else{fast = headB; //快指针指向Bslow = headA; //慢指针指向Astep = lenB - lenA; //步数为B的长度减去A的长度}for (int i = 0; i < step; i++){fast = fast->next; //快指针先走step步}while (fast != NULL && slow != NULL) //若快慢指针都不为空{if(fast == slow) //若快慢指针相等{return fast; //返回快指针}fast = fast->next; //快指针走一步slow = slow->next; //慢指针走一步}
}

问题3：

解决方案：

用空间换时间。

由于节点的绝对值|data|≤n，所以可以创建一个n大小的数组，用于判断该节点的数值是否存在，用0或1表示。

如果在链表中存在±15的节点，那么在遍历链表时，第一次遇到±15时，则在数组中，将数组下标为15的值赋值为1，表示之前在链表中出现了绝对值为15的节点。之后遇到绝对值为15的节点，都通过判断数组下标为15的值为1，删除掉后续绝对值为15的链表节点。（比较绕，建议多读几遍。）

代码实现：

void removeNode(Node *L, int n)
{Node *p = L; //指向头节点int index = 0;int *q = (int *)malloc(sizeof(int)*(n+1)); //分配内存//遍历数组for(int i = 0; i < n+1; i++){*(q + i) = 0; //初始化}while(p->next != NULL){//ads获取绝对值index = abs(p->next->data); //获取绝对值if(*(q + index) == 0) //若为0{*(q + index) = 1; //赋值为1p = p->next; //指向下一个节点}else{Node *temp = p->next; //保存要删除的节点p->next = temp->next; //删除节点free(temp); //释放内存}}free(q); //释放内存}

问题4：

解决方案：

使用三个节点，如图所示，依次将second节点指向first节点，直到second节点为NULL，完成链表反转。

代码实现：

Node* reverseList(Node *head)
{Node *first  = NULL; //指向空Node *second = head->next; //指向第一个节点Node *third  = NULL; //指向空while(second != NULL){third = second->next; //保存下一个节点second->next = first; //第一个节点指向空first = second; //第一个节点指向第二个节点second = third; //第二个节点指向第三个节点}Node *hd = initList(); //初始化链表hd->next = first; //头节点指向第一个节点return hd; //返回头节点
}

问题5：

解决方案：

Fast指针初始指向第一个节点，Slow节点初始指向头节点，Fast每次走两个节点，Slow每次走一个节点，最后当Fast的下一个节点为NULL时，Slow的下一个节点就是中间节点，直接将Slow的下个节点指向下下个节点即可，然后记得释放掉Slow的下个节点的空间。

代码实现：

int delMiddleNode(Node *head)
{Node *fast = head->next; //快指针Node *slow = head; //慢指针while(fast != NULL && fast->next != NULL) //若快指针不为空{fast = fast->next->next; //快指针走两步slow = slow->next; //慢指针走一步}Node *q = slow->next; //保存要删除的节点slow->next = q->next; //删除节点free(q); //释放内存return 1;
}

问题6：

解决方案：

先找到中间节点。

然后将中间节点的后半段反转后，然后将两段链表互相插入。即：p1->q1->p2->q2。

代码实现：

void reOrderList(Node *head)
{Node *fast = head->next; //快指针Node *slow = head; //慢指针while(fast != NULL && fast->next != NULL) //若快指针不为空{fast = fast->next->next; //快指针走两步slow = slow->next; //慢指针走一步}//此时slow->next为中间节点//反转后半部分Node *first = NULL; //指向空Node *second = slow->next; //指向中间节点 后半段的第一个节点slow->next = NULL; //中间节点指向空Node *third = NULL; //指向空while(second != NULL) //若第二个节点不为空{third = second->next; //保存下一个节点second->next = first; //第二个节点指向空first = second; //第一个节点指向第二个节点second = third; //第二个节点指向第三个节点}Node *p1 = head->next; //指向第一个节点Node *q1 = first; //指向第一个节点Node *p2 = NULL; //指向空Node *q2 = NULL; //指向空while(p1 != NULL && q1 != NULL) //若p1和q1都不为空{p2 = p1->next; //保存上半段的下一个节点q2 = q1->next; //保存下半段的下一个节点p1->next = q1; //上半段的第一个节点指向下半段的第一个节点q1->next = p2; //下半段的第一个节点指向上半段的第二个节点p1 = p2; //指向上半段的下一个节点q1 = q2; //指向下半段的下一个节点}return 1;}

单链表-单向循环链表

例题：

判断链表是否有环。

解决方案：

快指针走两步，慢指针走一步

代码实现：

//判断链表是否有环int isCyscle(Node *head){Node *fast = head; //快指针Node *slow = head; //慢指针while (fast != NULL && fast->next != NULL) //若快指针不为空{fast = fast->next->next; //快指针走两步slow = slow->next; //慢指针走一步if(fast == slow) //若快慢指针相等{return 1; //返回1}}}