链表
在本文中，我将介绍几道链表相关的题目，由浅入深，有些题也比较巧妙，可以学到一些好的思想和解题方法。
Leetcode21 合并两个升序链表
将两个升序链表合并成一个新的升序链表并返回。
代码部分
ListNode *MergetwoList(ListNode*head1,ListNode*head2)
{
ListNode*dummy=new ListNode(0);
ListNode*p=dummy;
while(head1 && head2)
{
if(head1->val<head2->val)
{
p->next=new ListNode(head1->val);
head1=head1->next;
}
else
{
p->next=new ListNode(head2->val);
head2=head2->next;
}
p=p->next;
}
p->next=head1?head1:head2;
return dummy->next;
}- 若head1和head2均不空，则取较小的，之后直接p->next=head1?head1:head2把剩下的那部分接过来
Leetcode 147 对链表进行插入排序
由于链表本身就是连着的，对其进行插入排序需要重点考虑的是一些指针应该怎么变换
ListNode *insertionSortlist(ListNode*head)
{
if(head==nullptr) {return nullptr;}
ListNode*dummyHead=new ListNode(0);
dummyHead->next=head;
ListNode*lastSort=head;
ListNode*curr=dummyHead->next->next;
while(curr)
{
if(lastSort->val<curr->val) {lastSort=lastSort->next;}
else
{
ListNode*pre=dummyHead;
while(pre->next->val<curr->val)
{
pre=pre->next;
}
lastSort->next=curr->next;
curr->next=pre->next;
pre->next=curr;
}
curr=lastSort->next;
}
return dummyHead->next;
}- 此方法中用到了三个指针，一个是curr，就是目前该排序的节点，一个是lastSort，代表着在这个指针之前的已经是已序的了，还有是一个pre,他的作用是为了帮助curr，找到他应该放到哪里。
- 不好整的就是找到这个节点该插到哪里后，这些指针的指向应该怎么变化。这里我总结了一个小方法：从前向后看，正确的状态应该是pre->curr,curr->pre->next,lastSort->next=curr->next。那么写code的时候就从后往前写，先有lastSort->next=curr->next，再curr->next=pre->next，最后pre->next=curr，这样就不会有野指针出现了（应该是这样，我也不是百分之百确定，百分之九十九确定）。
Leetcode23 合并K个升序链表
在上上节中介绍了一个桶排序，当时是把数值分配到了若干个桶中，将每个桶中的数值排序后再进行合并，其中每个桶中排序好的数据就是一个升序链表，当时合并的方法比较简单粗暴，就是1与2先合并，然后再与3合并，依次类推。
这里介绍一种分治合并，和归并排序的思想有点像，先两两合并，合并后链表的长度减半，再两两合并，直到最终只有一个链表。
ListNode *mergeTwoLists(ListNode*head1,ListNode*head2)
{
ListNode*dummy=new ListNode(0);
ListNode*p=dummy;
while(head1 &&head2)
{
if(head1->val<head2->val)
{
p->next=new ListNode(head1->val);
head1=head1->next;
}
else
{
p->next=new ListNode(head2->val);
head2=head2->next;
}
p=p->next;
}
p->next=head1?head1:head2;
return dummy->next;
}
ListNode *merge(vector<ListNode*>&lists,int l,int r)
{
if (l==r) return lists[l];
if (l>r) return nullptr;
int mid=(l+r)>>1;
return mergeTwoLists(merge(lists,l,mid),merge(lists,mid+1,r));
}
ListNode *mergeKLists(vector<ListNode*>&lists)
{
return merge(lists,0,lists.size()-1);
}Leetcode141 环型链表
该题有两种比较合适的解法
- 快慢指针，一个指针一次走一步，另一个指针一次走两步，如果链表中有环的话，那么一定会在环中的某个结点相遇
- 哈希表，从链表的头结点开始遍历，把遍历过的节点均放到哈希表中，如果是循环链表的话，那么哈希表中就一定会出现重复的节点。
1.快慢指针法:
bool CycleList(ListNode*head)
{
if(head==nullptr || head->next==nullptr)
{
return false;
}
ListNode*slow=head;
ListNode*fast=head->next;
while(slow!=fast)
{
if(fast==nullptr || fast->next==nullptr)
{
return false;
}
slow=slow->next;
fast=fast->next->next;
}
return true;
}2.哈希表法
bool hasCycle(ListNode*head)
{
unordered_set<ListNode*>seen;
while(head)
{
if(seen.count(head)) return true;
seen.insert(head);
head=head->next;
}
return false;
}leetcode160 相交链表
给你两个但链表的头结点headA和headB，请你找出并返回两个单链表相交的起始节点，两个链表不存在相交节点，返回null
- 很明显，此题如果要是用哈希表的话直接就秒了，先把第一个链表遍历一遍，把所有的节点都装到哈希表，再遍历另一个链表，如果其中的节点在哈希表中是存在的，那么就是相交链表。
- 还有一种非常巧妙的双指针的方法，A链表表示成a+c,B链表表示成b+c,一个指针先把A遍历一遍后再去遍历B，另一个先把B遍历一遍后再去遍历A，这样一定会在走了a+b+c步之后相遇(如果两个链表没有相交的部分则可以把两个链表理解成a+nullptr,b+nullptr,他们在走了a+b步之后都是nullptr)。
ListNode*getIntersectionNode(ListNode *headA, ListNode *headB)()
{
if(headA==nullptr ||headB==nullptr) return nullptr
ListNode*pA=headA;
ListNode*pB=headB;
while(pA!=pB)
{
pA=pA==nullptr?headB:pA->next;
pB=pB==nullptr?headA:pB->next;
}
return pA;
}用一句话来形容这个方法：我走过你走过的路，只为与你相拥。
Leetcode19 删除链表中的倒数第N个节点
给你一个链表，删除链表的倒数第n个节点，并返回头结点。
- 一种比较自然的想法是先看看链表中一共有多少节点（m），删除倒数第n个也就意味着是正数第(m-n+1)个
- 另一种方法自然就是双指针了，双指针在链表中的运用比较多。先设置一个dummy，指向head,让两个指针(p1,p2)指向dummy。先让p1走n步，然后两个指针再一起走，p1指向最后一个节点的时候，p2->next就是要删除的节点了。
ListNode* removeNthFromEnd(ListNode* head, int n)
{
ListNode *dummy=new ListNode(0);
dummy->next=head;
ListNode*p1=dummy;
ListNode*p2=dummy;
for(int i=0;i<n;i++)
{
p1=p1->next;
}
while(p1->next)
{
p1=p1->next;
p2=p2->next;
}
p2->next=p2->next->next;
return dummy->next;
}Leetcode876链表的中间节点
给你一个单链表，请你找出并返回链表的中间节点，如果有两个中间节点，则返回第二个。
- 用快慢指针的方法，一个指针一次走一步，另一个指针一次走两步。
ListNode *middle(ListNode*head)
{
ListNode *p1=head;
ListNode *p2=head;
while(p2 &&p2->next)
{
p1=p1->next;
p2=p2->next->next;
}
return p1;
}如果对于有两个中间节点的链表，我想返回第一个应该怎么办？仔细观察一下，我们只要更改一下while循环中的条件即可,换成(p->next &&p->next->next)。
Leetcode143重排链表
给定一个单链表L的头结点head,单链表L表示为:
$$
L_1->L_2->…->L_{n-1}->L_{n}
$$
请将其重新排列后变为:
$$
L_0->L_n->L_1->L_{n-1}->L_2->L_{n-2}->…
$$
不能只是单纯的改变结点内部的值，而是需要世界的进行结点交换。
- 把原来的链表改成前面取一个后面取一个，以此类推。先找到链表的中间节点，将链表分成两部分，把后面的那部分链表反转一下，然后再合并两个链表。此题步骤相对较多，可以帮助巩固一些基本的操作。
ListNode *middleNode(ListNode*head)
{
ListNode*slow=head;
ListNode*fast=head;
while(fast->next && fast->next->next)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode*reverseList(ListNode*head)
{
ListNode*prev=nullptr;
ListNode*curr=head;
while(curr)
{
prev=new ListNode(curr->val,prev);
curr=curr->next;
}
return prev;
}
void mergeList(ListNode*l1,ListNode*l2)
{
ListNode*l1_tmp;
ListNode*l2_tmp;
while(l1!=nullptr && l2!=nullptr)
{
l1_tmp=l1->next;
l2_tmp=l2->next;
l1->next=l2;
l1=l1_tmp;
l2->next=l1;
l2=l2_tmp;
}
}
void reorderList(ListNode*head)
{
if(head==nullptr)
{
return;
}
ListNode*mid=middleNode(head);
ListNode*l1=head;
ListNode*l2=mid->next;
mid->next=nullptr;
l2=reverseList(l2);
mergeList(l1,l2);
}Leetcode2 两数相加
给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
示例：
$$
2->4->3 \
5->6->4 \
7->0->8 \
$$
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2)
{
ListNode *Hwikb=new ListNode(0);
ListNode *current=Hwikb;
int flag=0;
while(l1 ||l2||flag)
{
int sum=0;
sum+=flag;
if(l1)
{
sum+=l1->val;
l1=l1->next;
}
if(l2)
{
sum+=l2->val;
l2=l2->next;
}
flag=sum/10;
current->next=new ListNode(sum%10);
current=current->next;
}
return Hwikb->next;
}专门为大于10的节点立了一个flag，相当巧妙。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Hwikb！
评论