沈阳德泰诺网站建设公司,成都网站制作售后,上海网站制作公司哪家,网站运营与管理的目的是文章目录1.链表逆序1.1 题目描述1.2链表逆序的C实现2.反转链表2.1 题目描述2.2 反转链表的C实现3.求两个链表的交点3.1 题目描述3.2 C实现——set3.3 C语言实现——链表长度实现4.链表求环4.1 题目描述4.2 C实现4.3 C语言实现——快慢指针5.分隔链表5.1 题目描述5.2 C实现6.复制…
文章目录1.链表逆序1.1 题目描述1.2链表逆序的C实现2.反转链表2.1 题目描述2.2 反转链表的C实现3.求两个链表的交点3.1 题目描述3.2 C实现——set3.3 C语言实现——链表长度实现4.链表求环4.1 题目描述4.2 C实现4.3 C语言实现——快慢指针5.分隔链表5.1 题目描述5.2 C实现6.复制带随机指针的链表6.1 题目描述6.2 C实现7.排序链表的合并7.1 题目描述7.2 C实现8.多个排序链表的合并8.1 题目描述8.2 C实现8.3 C实现——分治1.链表逆序
1.1 题目描述 反转一个单链表。 示例: \qquad输入: 1-2-3-4-5-NULL \qquad输出: 5-4-3-2-1-NULL 1.2链表逆序的C实现
#includeiostream
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* new_head NULL;while (head) {ListNode* next;next head-next;head-next new_head;new_head head;head next;}return new_head;}
};2.反转链表
2.1 题目描述 给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。 2.2 反转链表的C实现
struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {int change_len right-left1;ListNode *pre_headNULL;ListNode *resulthead;while(head--left){pre_headhead;headhead-next;}ListNode *modify_list_tailhead;ListNode *new_headNULL;while(headchange_len){ListNode *nexthead-next;head-nextnew_head;new_headhead;headnext;change_len--;}modify_list_tail-nexthead;if(pre_head){pre_head-nextnew_head;}else{resultnew_head;}return result;}
};3.求两个链表的交点
3.1 题目描述 编写一个程序找到两个单链表相交的起始节点。 3.2 C实现——set
struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {setListNode* Node_set;while(headA){Node_set.insert(headA);headAheadA-next;}while(headB){if(Node_set.find(headB)!Node_set.end()){return headB;}headBheadB-next;}return NULL;}
};3.3 C语言实现——链表长度实现 步骤1计算headA和headB的长度 步骤2将较长链表的指针移动到和较短链表指针对齐的地方 步骤3两个链表同时移动当两者指向同一个结点时结点被找到 int get_list_legth(struct ListNode *head){int len0;while(head){len;headhead-next;}return len;}struct ListNode *forward_long_list(int long_len,int short_len,struct ListNode *head){int deltalong_len-short_len;while(headdelta){headhead-next;delta--;}return head;}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {int list_A_lenget_list_legth(headA);int list_B_lenget_list_legth(headB);if(list_A_lenlist_B_len){headAforward_long_list(list_A_len,list_B_len,headA);}if(list_B_lenlist_A_len){headBforward_long_list(list_B_len,list_A_len,headB);}while(headAheadB){if(headAheadB){return headA;}headAheadA-next;headBheadB-next;}return NULL;
}4.链表求环
4.1 题目描述 给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null。 为了表示给定链表中的环我们使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。 如果 pos 是 -1则在该链表中没有环。注意pos 仅仅是用于标识环的情况并不会作为参数传递到函数中。 4.2 C实现
class Solution {
public:ListNode *detectCycle(ListNode *head) {setListNode * node_list;while(head){if(node_list.find(head)!node_list.end()){return head;}node_list.insert(head);headhead-next;}return NULL;}
};4.3 C语言实现——快慢指针
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fasthead;struct ListNode *slowhead;while(fast!NULL){slowslow-next;if(fast-nextNULL){return NULL;}fastfast-next-next;if(fastslow){struct ListNode *ptrhead;while(ptr){if(ptrslow){return ptr;}ptrptr-next;slowslow-next;} }}return NULL;
}5.分隔链表
5.1 题目描述 给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你应当 保留 两个分区中每个节点的初始相对位置。 5.2 C实现
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode less_head(0);ListNode more_head(0);ListNode *less_ptrless_head;ListNode *more_ptrmore_head;while(head){if(head-valx){less_ptr-nexthead;less_ptrhead;}else{more_ptr-nexthead;more_ptrhead;}headhead-next;}less_ptr-nextmore_head.next;more_ptr-nextNULL;return less_head.next;}
};6.复制带随机指针的链表
6.1 题目描述
题目描述
6.2 C实现
#includeiostream
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:Node* copyRandomList(Node* head) {mapNode *,int node_map;vectorNode * node_vec;Node *ptrhead;int i0;while(ptr){node_map[ptr]i;node_vec.push_back(new Node(ptr-val));ptrptr-next;i;}node_vec.push_back(0);ptrhead;i0;while(ptr){node_vec[i]-nextnode_vec[i1];if(ptr-random){int idnode_map[ptr-random];node_vec[i]-randomnode_vec[id];}ptrptr-next;i;}return node_vec[0];}
};7.排序链表的合并
7.1 题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 7.2 C实现
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode temp_head(0);ListNode *pretemp_head;while(l1l2){if(l1-vall2-val){pre-nextl1;l1l1-next;}else{pre-nextl2;l2l2-next;}prepre-next;}if(l1){pre-nextl1;}if(l2){pre-nextl2;}return temp_head.next;}
};8.多个排序链表的合并
8.1 题目描述 给你一个链表数组每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中返回合并后的链表。 8.2 C实现
bool cmp(ListNode *a,ListNode *b){return a-valb-val;}
class Solution {
public:ListNode* mergeKLists(vectorListNode* lists) {vectorListNode * node_vec;int i;for(i0;ilists.size();i){ListNode *headlists[i];while(head){node_vec.push_back(head);headhead-next;}}if(node_vec.size()0){return NULL;}sort(node_vec.begin(),node_vec.end(),cmp);for(i1;inode_vec.size();i){node_vec[i-1]-nextnode_vec[i];}node_vec[node_vec.size()-1]-nextNULL;return node_vec[0];}
};8.3 C实现——分治
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {ListNode temp_head(0);ListNode *pretemp_head;while(l1l2){if(l1-vall2-val){pre-nextl1;l1l1-next;}else{pre-nextl2;l2l2-next;}prepre-next;}if(l1){pre-nextl1;}if(l2){pre-nextl2;}return temp_head.next;}ListNode* mergeKLists(vectorListNode* lists) {if(lists.size()0){return NULL;}if(lists.size()1){return lists[0];}if(lists.size()2){return mergeTwoLists(lists[0],lists[1]);}int midlists.size()/2;vectorListNode * sub1_lists;vectorListNode * sub2_lists;int i;for(i0;imid;i){sub1_lists.push_back(lists[i]);}for(imid;ilists.size();i){sub2_lists.push_back(lists[i]);}ListNode *l1mergeKLists(sub1_lists);ListNode *l2mergeKLists(sub2_lists);return mergeTwoLists(l1,l2);}
};
