当前位置：首页 > news >正文

【LeetCode热题100】链表

news 2024/10/27 13:16:54

这篇博客记录了关于链表的几道题目：两数相加、两两交换链表中的节点、K个一组反转链表、合并K个升序链表。

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1,*cur2 = l2;ListNode* head = new ListNode; //创建哨兵位ListNode* tail = head; //尾指针int t = 0; // 记录进位 while(cur1 || cur2 || t) //都走完了，t可能不为0{//先加第一个链表if(cur1 != nullptr){t += cur1->val;cur1 = cur1->next;}//再加第二个链表if(cur2 != nullptr){t += cur2->val;cur2 = cur2->next;}tail->next = new ListNode(t % 10);tail = tail->next;t /= 10;}tail = head->next;delete head;//释放头结点return tail;}
};

题目分析：题目给出的逆序的数字，这刚好，因为求和就是从低位开始的，然后就要创建一个哨兵位头结点，比较方便，然后创建变量t用于保存相同位相加的结果，取其个位创建新节点尾插，t的十位继续和下一位的相加。

class Solution {
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead = new ListNode();newhead->next = head;ListNode* prev = newhead,*cur = prev->next,*_next = cur->next,*nnext = _next->next;while(cur && _next){//1.交换节点prev->next = _next;_next->next = cur;cur->next = nnext;//2.修改指针prev = cur;cur = nnext;if(cur) _next = cur->next;if(_next) nnext = _next->next;}  cur = newhead->next;delete newhead; return cur;}
};

题目分析：需要创建一个哨兵位节点，并且为需要变动的节点都分配一个名字，这样比较好修改，当有偶数个时，cur为空就结束，当有奇数个时，next为空就结束。最终要释放申请的哨兵位。

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {int sum = 0;ListNode* cur = head;//1.先求出要逆序多少组while(cur){sum++;cur = cur->next;}int num = sum / k;//2.重复n次，长度为k的链表的逆序即可ListNode* newhead = new ListNode();ListNode* tmp = newhead; // 下一次要头插的节点cur = head;ListNode* prev = head;while(num--){prev = cur; // 保存下一次头插的节点for(int i = 0; i < k ; i++){ListNode* next = cur->next;cur->next = tmp->next;tmp->next = cur;cur = next;}tmp = prev;}//把不需要逆序的接上  tmp->next = cur;ListNode* ret = newhead->next;delete newhead;return ret;}};

题目分析：分为两步，第一步：先求出需要逆序多少组，第二步：重复n次，长度为k的链表的逆序即可。采用头插法逆序。也就是两层循环，第一层是循环组数次，第二层是循环k次头插。需要注意的是，第二层每次循环前，需要记录下一次要被头插的元素。

//1.解法1
class Solution 
{struct cmp{bool operator()(const ListNode* l1,const ListNode* l2){return l1->val > l2->val;}};
public:ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*,vector<ListNode*>,cmp> pq;for(auto list : lists){if(list) pq.push(list);}ListNode* newhead = new ListNode(0);ListNode* prev = newhead;while(!pq.empty()){ListNode* top = pq.top();pq.pop();prev->next = top;prev = prev->next;if(top->next) pq.push(top->next);}prev = newhead->next;delete newhead;return prev;}
};
//2.解法2
class Solution 
{ListNode* _mergeKLists(vector<ListNode*>& list,int left,int right){if(left > right) return nullptr;if(left == right) return list[left];int mid = (left + right) >> 1;//[left,mid][mid+1,right]ListNode* l1 = _mergeKLists(list,left,mid);ListNode* l2 = _mergeKLists(list,mid+1,right);return MergeTwoList(l1,l2);}ListNode* MergeTwoList(ListNode* l1,ListNode* l2){if(l1 == nullptr) return l2;if(l2 == nullptr) return l1;ListNode head;head.next = nullptr;ListNode* prev = &head;ListNode* cur1 = l1,*cur2 = l2;while(cur1 && cur2){if(cur1->val < cur2-> val){prev->next = cur1;cur1 = cur1->next;prev = prev->next;}else{prev->next = cur2;cur2 = cur2->next;prev = prev->next;}}if(cur1) prev->next = cur1;if(cur2) prev->next = cur2;return head.next;}
public:ListNode* mergeKLists(vector<ListNode*>& lists) {return _mergeKLists(lists,0,lists.size()-1);}
};