【LeetCode热题100】链表
这篇博客记录了关于链表的几道题目:两数相加、两两交换链表中的节点、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);
}
};
题目分析:
解法1:
这道题的思路是利用优先级队列,创建小堆的优先级队列,先将所有链表的第一个元素放到优先级队列中,然后取出堆顶元素,然后pop,再把刚才堆顶所在链表的下一个元素插入到优先级队列中,依次类推。
解法2:
也可以使用分治递归的思想进行解决,其解决思路类似分治排序。