竹子建站模板怎么下载,哪些企业需要网站建设,wordpress用户邮箱验证码,WordPress开通用户投稿功能文章目录 前言一、移除链表元素二、链表的中间节点三、合并两个有序链表四、反转链表五、链表分割六、倒数第k个节点总结 前言
leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍 一、移除链表元… 文章目录 前言一、移除链表元素二、链表的中间节点三、合并两个有序链表四、反转链表五、链表分割六、倒数第k个节点总结 前言
leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍 一、移除链表元素 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {ListNode* newhead NULL;ListNode* newtail NULL;ListNode* cur head;while(cur){if(cur-val ! val){if(newhead NULL){newhead newtail cur;}else{newtail-next cur;newtail newtail-next;}cur cur-next;}else{ListNode* next cur-next;free(cur);cur next;}}if(newtail)newtail-next NULL;return newhead;
}遍历链表若节点的值不等于给定的值则尾插到新链表后面。若等于则跳过。
二、链表的中间节点 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {ListNode* fast head, *slow head;while(fast ! NULL fast-next ! NULL){fast fast-next-next;slow slow-next;}return slow;}快慢指针快指针一次走两步。慢指针一次走一步。当快指针节点为空或者下一个节点为空时跳出循环。此时慢指针指向中间节点。
三、合并两个有序链表 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1 NULL list2 NULL){return NULL;}ListNode* newHead , *newTail;newHead newTail NULL;while(list1 ! NULL list2 ! NULL){if(list1-val list2-val){if(newHead NULL){newHead newTail list2;}else{newTail-next list2;newTail newTail-next;}list2 list2-next;}else{if(newHead NULL){newHead newTail list1;}else{newTail-next list1;newTail newTail-next;}list1 list1-next;}}if(list1 NULL){if(newHead NULL)newHead list2;elsenewTail-next list2;}else{if(newHead NULL)newHead list1;elsenewTail-next list1;}return newHead;
}遍历两个单链表。两个链表都不为空判断节点大小将小点节点尾插到新的头节点上。若有一个链表为空跳出循环并将另一个链表尾插到新的尾节点上。
四、反转链表 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head NULL)return NULL;ListNode* n1, *n2, *n3;n1 NULL;n2 head;n3 head-next;while(n2){n2-next n1;n1 n2;n2 n3;if(n3)n3 n3-next;}return n1;
}将每个节点的next指向前一个节点。 创建一个新的头节点遍历链表进行头插。
五、链表分割 /*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* gGuard, *gTail, *lGuard, *lTail;gGuard gTail (struct ListNode*)malloc(sizeof(struct ListNode));lGuard lTail (struct ListNode*)malloc(sizeof(struct ListNode));gGuard-next lGuard-next NULL;struct ListNode* cur pHead;while(cur){if(cur-val x){lTail-next cur;lTail lTail-next;}else {gTail-next cur;gTail gTail-next;}cur cur-next;}lTail-next gGuard-next;gTail-next NULL;pHead lGuard-next;free(gGuard);free(lGuard);return pHead;}
};创建两个带有哨兵位的单向链表。若小于给定值尾插到小的链表中。若大于等于给定值尾插到大的链表中。再将小链表的尾节点的next指向大链表的第一个有效节点。最后再将大链表的尾节点的next指向NULL。
六、倒数第k个节点
输入一个链表输出该链表中倒数第k个结点。
#include stdio.h
#include stdlib.htypedef struct ListNode
{int val;struct ListNode* next;
}ListNode;ListNode* FindKthToTail(ListNode* pListHead, int k)
{if (pListHead NULL){return NULL;}ListNode* fast, * slow;fast slow pListHead;int i 0;for (i 1; i k; i){fast fast-next;if (fast NULL){return NULL;}}while (fast-next ! NULL){fast fast-next;slow slow-next;}return slow;
}int main()
{ListNode* phead (ListNode*)malloc(sizeof(ListNode));ListNode* n2 (ListNode*)malloc(sizeof(ListNode));ListNode* n3 (ListNode*)malloc(sizeof(ListNode));ListNode* n4 (ListNode*)malloc(sizeof(ListNode));ListNode* n5 (ListNode*)malloc(sizeof(ListNode));phead-val 1;n2-val 2;n3-val 3;n4-val 4;n5-val 5;phead-next n2;n2-next n3;n3-next n4;n4-next n5;n5-next NULL;ListNode* plist phead;ListNode* ret FindKthToTail(plist,5);while (ret){printf(%d-, ret-val);ret ret-next;}printf(NULL\n);return 0;
}倒数第k个和倒数第一个之间的距离是k-1.所以使用快慢指针将快的指针先走k-1步此时快慢指针差距是k-1.所以当快指针走到链表结尾时慢指针走到倒数第k个节点。 总结
leetcode以及牛客网单链表相关的题、移除链表元素、链表的中间节点、合并两个有序链表、反转链表、链表分割、倒数第k个节点等的介绍
