链表相关问题
第206题 反转链表
要求:将给定链表进行反转操作,第一个结点作为尾结点,第二个结点指向第一个节点,以此类推,使得原链表的尾结点作为答案的头结点。
思路一:逐步操作
1)设置结点prev(初始化为null)
2)从头结点开始,记录当前结点(cur)的下一个结点(next),将cur指向prev后,prev前移一个(对于新链而言前移),cur后移一个到被记录的next上(对于原链而言后移)
3)当cur在原链表上已被后移到null时,结束循环
这种方法更加重要。
ListNode* reverseList1(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
思路二:巧用栈
1)定义一个stack
2)从头结点开始依次入栈,直至链尾
3)栈内结点依次出栈,让新链表的链尾每次都指向栈顶结点,直至栈空
ListNode* reverseList2(ListNode* head) {
stack<ListNode*> s1;
ListNode* cur1 = head;
while (cur1) {
s1.push(cur1);
cur1 = cur1->next;
}
ListNode* tmp = new ListNode(0);
ListNode* ans = tmp;
while (!s1.empty()) {
tmp->next = s1.top();
tmp = tmp->next;
s1.pop();
}
tmp->next = nullptr;
return ans->next;
}
第61题 旋转链表
要求:给定一个链表的头节点head,旋转链表,将链表每个节点向右移动 k 个位置,每移动一次,都让当前链表的尾结点指向头结点,倒数第二个结点成为尾结点。
分析过程:
1)若链表一共有m个结点,旋转一次后,第m个结点成为头结点;旋转两次后,第m-1个结点成为头结点,旋转k(k≤m-1)次后,m-k+1个结点成为头结点。旋转m次后,原链表头结点将再次成为头结点。
2)旋转链表是一个循环操作,即对于所有的k(k除以m的余数相同),旋转k次,得到的链表头结点相同
解题思路
1)找到链表的节点个数(count)
2)取k除以count的余数,即为缩小的旋转次数
3)头结点为第count-k+1个,使用for循环找到该结点
4)改变相应结点的next指针,得到新链表
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return nullptr;
ListNode* tmp1 = head;
int count = 1;
while (tmp1->next != nullptr) {
tmp1 = tmp1->next;
count++;
}
tmp1->next = head;
tmp1 = head;
k = k % count;
for (int i = 0; i < count - k - 1; i++) {
tmp1 = tmp1->next;
}
head = tmp1->next;
tmp1->next = nullptr;
return head;
}
第141题 环形链表I
要求:判断链表是否有环。
思路一:通过判断结点是否在遍历过程中重复出现来判断是否成环
1)从头开始依次遍历链表,建立unoredered_set,将结点放入set中
2)放入结点前判断结点是否已经存在于set中,若存在则说明成环,直接返回;若不存在则放入
3)若将整个链表遍历完成,仍未发现链表中存在重复结点,则说明链表无环
bool hasCycle1(ListNode* head) {
unordered_set<ListNode*> s;
if (!head) return false;
while (head) {
if (s.count(head))return true;
s.insert(head);
head = head->next;
}
return false;
}
思路二:使用快慢指针
快慢指针是一种解决链表问题的常用手段,常用于寻找链表的中间结点、链表的环内操作等。
Tip:使用快慢指针找中间结点的方法。
ListNode* findMid(ListNode* head) {
ListNode* slow = head, * fast = head;
while (fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
1)快慢指针均被初始化为head结点,之后快指针每次往后走两步,慢指针每次往后走一步;
2)若快慢指针会相遇,则说明有环存在。显然,快慢指针在一条非循环单链表中是不可能相遇的。注意:若存在环,则快慢指针一定会在环内相遇,二者互为充要条件。
bool hasCycle2(ListNode* head) {
ListNode* fast = head, * slow = head;
if (head == nullptr || head->next == nullptr)return false;
while (fast != nullptr && fast->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow)return true;
}
return false;
}
思路三:遍历链表,使用标记的思想
1)遍历链表,如果当前结点没有指向它自己,就让它指向自己
2)如果当前结点指向了自己,则说明这个结点之前被操作过,则链表存在环
注意:如果链表只有一个结点,则不可能有环,直接返回
一个很有趣的比喻:假设在森林里有许多棵树,树与树之间有绳子连接,你在森林里沿着绳子一棵棵树往前走,每碰到一棵树就在树上写下自己的名字,如果发现前面那棵树上有自己的名字,即说明存在环。**
bool hasCycle3(ListNode* head) {
if (!head || head->next == nullptr)return false;
if (head->next == head)return true;
ListNode* next = head->next;
head->next = head;
return hasCycle3(next);
}
思路四:将链表反转,如果尾结点与头结点一样,则说明有环
在反转链表的函数中,如果遍历到nullptr,则停止。这样会有一个疑惑,循环链表不应该会有nullptr出现,那怎么找到循环链表所谓的反转链表呢?
其实,根据reverseList1函数的思想,最开始我们会让head指向nullptr,在遍历的过程中,很多结点的next指针已经在新链表中发生变化,这样一来遍历的时候出现nullptr就不奇怪了。
举个例子:
例如有这样一个链表,1指向2,2指向3,3指向4,4指向2(开始循环)。(1是头结点)
反转过程:
- 初始化一个null,1指向null,2指向1,3指向2,4指向3,那么下一个就会让4指向的结点,来指向4,也就是2指4。
- 接下来,next会是cur(2)的next属性,也就是新链表中的1,然后让2指向4,prev为cur也就是2,cur变为新next也就是1。
- 再下一次,next值变为cur的next属性,也就是1的next为null,再让1指向2,prev变为1,cur变为null。
- 最后,由于cur已经为null,将退出while循环。
这种方法特别巧妙,建议使用断点调试一下整个运行过程,会更加清晰,代码如下(reverseList1())在上文已给出:
bool hasCycle4(ListNode* head)
{
if (head == reverseList1(head)) return true;
return false;
}
第142题 环形链表II
要求:在一个存在环的链表中,找到成环的第一个结点。
这道题利用了比较强的算法思想:使用快慢指针时,当二者相遇的时候,相遇结点与成环结点的距离,与头结点到成环结点的距离相等。
分析过程
使用数学方法来简单说明一下:
1)设头结点到成环结点的距离为a,从成环结点沿着next方向到相遇结点的距离为b,从相遇结点沿着next方向回到成环结点的距离为c
2)设相遇时slow指针走了x步,则fast指针走了2x步
3)显然,对于slow指针,x=a+b;对于fast指针,2x=a+b+c+b
4)由此观之,a=c
解题过程
1)使用快慢指针判断是否有环,有环则继续
2)判断有环即为二者相遇,相遇时保持fast的位置,让slow回到head
3)二者同时往前,再次相遇时即为成环的第一个结点
ListNode* detectCycle(ListNode* head) {
ListNode* fast = head, * slow = head;
bool hasCycle = false;
while (fast != nullptr && fast->next != nullptr && fast->next->next != nullptr) {
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
hasCycle = true;
break;
}
}
if (hasCycle) {
slow = head;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
}
return nullptr;
}
第21题 合并两个有序链表
要求:将两个升序链表合并为一个新的升序链表并返回。
解题过程:逐步遍历
1)首先创建虚拟头结点,将其赋值给cur
2)用两个指针分别代表两个链表的结点
3)每次比较当前两个结点的元素大小,得到元素值较小的结点
4)记录该结点的next结点,将该结点放到ans中,取完后将指针移到next结点上,cur结点后移(cur为ans的尾结点)
5)注意:如果有一个链表以及遍历到尾,另一个链表未到尾端,则直接让指针指向未到尾端链表的当前结点,将该链表之后的部分直接移解到ans中
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* dummy = new ListNode();
ListNode* cur = dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
cur->next = list1;
cur = cur->next;
list1 = list1->next;
}
else {
cur->next = list2;
cur = cur->next;
list2 = list2->next;
}
}
cur->next = list1 == nullptr ? list2 : list1;
return dummy->next;
}
第203题 移除链表元素
要求:给定链表和一个val值,删除值为val的所有结点。
思路一:使用逐步遍历的迭代思想
分析: 使用虚拟头结点,每次碰到当前结点的下一个结点元素值为val,就让该结点指向下下个结点,达到删除结点的目的。
解题过程:
1)创建虚拟头结点dummy,并让其指向head
2)用pre表示当前结点的前一个结点(从dummy开始),用cur表示当前结点(从head开始)
3)当cur值为val时,让pre的next为cur的next,并让将cur的next结点赋值为cur
4)若cur值不为val,则pre与cur均往下走一步,直到cur走到nullptr停止遍历
ListNode* removeElements1(ListNode* head, int val) {
ListNode* dummy = new ListNode(0, nullptr);
dummy->next = head;
if (!head) return nullptr;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur) {
if (cur->val == val) {
pre->next = cur->next;
cur = cur->next;
continue;
}
pre = pre->next;
cur = cur->next;
}
return dummy->next;
}
思路二:使用化长为短的递归思想
分析:递归是解决链表问题的常见方法。在这里,如果把当前head之后的链表完成了移除元素的操作,再处理当前的head,即可完成对整个链表操作
1)递归的终止条件:当前结点的值为空
2)递归的单层逻辑:每一次递归,都要把当前结点之后的链表完成移除操作
注意 如果每次递归链表的head结点为空,都需要将head移除,即把head的next结点作为头结点进行返回,达到移除head操作
ListNode* removeElements2(ListNode* head, int val) {
if (!head) return nullptr;
head->next = removeElements2(head->next, val);
if (head->val == val)return head->next;
return head;
}
第160题 相交链表
要求:给定两个链表,求出二者相交的起始结点,不存在则返回null。
思路一:双指针遍历
让两个指针分别从两个链表头开始遍历,如果二者长度不同,如何才能相遇(在相交结点)?
如果两条链表合在一起就好了!
但是,将二者合并是不现实的,于是,采用一个特殊的方法:双指针逐步遍历,当其到达某条链表的结尾时,让其移到另一条链表头继续遍历。
这样一来,两个指针分别走了两条链表不相交的部分,以及相交的部分各一次(可以理解为各走了三段路),二者步长相同,则会在初次相交的结点相遇。
ListNode* getIntersectionNode1(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode* pA = headA, * pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
思路二:使用set记录
这种方法就比较直接了,同样也易于理解
1)第一次遍历第一条链表,将每个结点记录在set中
2)第二次遍历第二条链表,如果当前结点在set的计数值count为1,说明该结点在第一条链表中出现过,第一个出现过的结点即为相交结点
3)若均不存在,则两条链表不相交
ListNode* getIntersectionNode2(ListNode* headA, ListNode* headB) {
unordered_set<ListNode*>first;
ListNode* temp = headA;
while (temp)
{
first.insert(temp);
temp = temp->next;
}
temp = headB;
while (temp)
{
if (first.count(temp)) return temp;
temp = temp->next;
}
return nullptr;
};
第143题 重排链表
要求:给定一个单链表 L 的头节点 head ,单链表 L 表示为:L0 → L1 → … → Ln-1 → Ln,重排后链表变为L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …。
解题思路:找尾结点、切割、反转、合并
1)若链表结点数不超过1,则直接返回
2)找尾结点:不难发现,如果原链表的结点数为奇数,那么重排链表的尾结点为原链表的中间结点;如果为偶数,那么尾结点为原链表的靠左的那个中间结点(中间结点有两个)
3)切割:将得到的尾结点(即中间结点)与原链表的后半部分分开,尾结点指向null,尾结点的原next结点为链表后半部分的头结点
4)反转:将链表后半部分反转,后半部分链表尾结点(也即原链表尾结点)作为后半部分链表的头结点
5)合并,两条链表合并,从将第二条链表插入原链表左半部分
void reorderList(ListNode* head)
{
if (head->next == nullptr || head->next->next == nullptr) return;
ListNode* ans = findMid(head);
ListNode* node2 = ans->next;
ans->next = nullptr;
node2 = reverseList1(node2);
ListNode* node1 = head;
while (node1 && node2) {
ListNode* node3 = node2;
node2 = node2->next;
ListNode* node4 = node1->next;
node1->next = node3;
node3->next = node4;
node1 = node4;
}
}
第148题 相交链表
要求:给定链表,按照升序排列后返回头结点。
解题思路:归并排序
排序算法非常之多,由于链表的特殊性质(按照顺序访问),使用归并排序来解决是个不错的思路,而归并排序本质上使用了递归的思想
1)找到中间结点,其next结点为后半部分链表的头结点
2)分别将左右两个部分排序后,将二者合并(合并函数在前文有提到)
递归的终止条件:该链表的结点数不超过1
递归的单层逻辑:找到中间结点,切割后分别排序,然后合并
ListNode* sortList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
if (head->next == nullptr) {
return head;
}
ListNode* mid = findMid(head);
ListNode* head2 = mid->next;
mid->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(head2);
return mergeTwoLists(left, right);
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)