本篇文章,将分享一些关于链表的算法题,来看看链表类型的算法题都该如何解决。
一.两数相加
来看题目(出自力扣):
题目很好理解,让我们将两个链表中对应位置的数相加,最后返回一个新的链表,实际上就是将两个整数相加,然后返回由结果的每一个位构成的链表。
这个题目较为简单,我们只需创建一个新的链表来作为结果,该链表初始携带一个哨兵位头结点,这样可以方便我们去进行链表的插入以及最后链表的返回,然后就是遍历两个链表去求和即可。
值得注意的是,因为是两个数之和,所以我们必须考虑进位问题,其次,两个链表的长度不一定相同,因此当一个链表遍历到结尾,另一个链表应继续完成遍历操作。
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* newhead = new ListNode(0);ListNode* temp = newhead;ListNode* cur1 = l1;ListNode* cur2 = l2;int sum = 0;while(cur1 || cur2){if(cur1){sum += cur1->val;cur1 = cur1->next;}if(cur2){sum += cur2->val;cur2 = cur2->next;}temp->next = new ListNode(sum % 10);temp = temp->next;sum /= 10;}if(sum != 0)temp->next = new ListNode(sum);temp = newhead->next;delete newhead;return temp;}
定义变量sum,如果sum的结果大于10,那么%10就是该位置的数字,/10就是进位,进位可以保留继续与后边的位数一起相加。
还有一点要注意的是,当两个链表都遍历结束时,sum仍然可能保存了一个进位,所以最后还需判断sum是否存在进位。
此外,newhead是一个临时变量,使用完之后应当及时delete,防止内存泄漏。
二.两两交换链表中的节点
来看题目(出自力扣):
题目要求我们将一个链表中每两个相邻的节点,交换它们的位置,注意,并不是交换节点中的值,而是要将整个节点都进行交换。
那么本题,我们创建一个空的哨兵位头结点之后在做是非常简单的,来看下图:
我们定义出四个指针,分别指向一次交换所需要接触到的四个节点,随后通过指针之间的相互交换,来完成节点之间的交换, 然后再重新更新四个指针的指向即可,如此循环执行,便可以完成本题。
注意,一次循环之后,我们需要找出循环结束的条件。很显然,在本题中,如果cur和next中有一个为nullptr,就不需要继续进行了。
ListNode* swapPairs(ListNode* head) {ListNode* newhead = new ListNode(0);newhead->next = head;ListNode* prev = newhead;ListNode* cur = prev->next;if(cur == nullptr)return nullptr;ListNode* next = cur->next;if(next == nullptr)return cur;ListNode* nnext = next->next;while(cur != nullptr && next != nullptr){prev->next = next;next->next = cur;cur->next = nnext;prev = cur;cur = nnext;if(cur)next = cur->next;if(next)nnext = next->next;}cur = newhead->next;delete newhead;return cur;}
在初始设置指针指向时,我们就应该及时的进行空指针的判断,一次循环之后,也应该进行空指针的判断。
三.合并k个升序链表
来看题目(出自力扣):
题意非常简单,就是让我们将k个有序链表合并成一个升序的链表。
第一想法,将所有的链表两个两个合并,但是这样的解法时间复杂度非常高,必然导致超时。
那么有没有更优秀的解法呢?
我们用到优先级队列,我们知道优先级队列的底层是堆,因此我们可以建个小堆,然后让所有的链表的第一个节点入堆,这样堆顶元素就是最小的节点,此时将堆顶元素拿走放入新的结果链表,再让该堆顶节点的下一个节点入堆,如此循环往复,直至堆为空。这样就能大大减少时间复杂度。
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> heap;//每个链表的头节点入堆for(auto l : lists){if(l)heap.push(l);}ListNode* newhead = new ListNode(0);ListNode* prev = newhead;//从小堆中取头节点到结果链表中while(!heap.empty()){ListNode* top = heap.top();heap.pop();prev->next = top;prev = top;//某个链表的节点出堆,让其下一个节点入堆if(top->next) heap.push(top->next);}prev = newhead->next;delete newhead;return prev;}
};
在解决链表算法时,比较关键的一点就是创建一个哨兵位头节点来处理题目给出的链表,链表相关的算法就分享到这里。