核心知识点
null异常处理
dummy node 哑巴节点
双指针/快慢指针
插入一个节点到排序链表
从一个链表中移除一个节点
翻转链表
合并两个链表
找到链表的中间节点
例题:
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
直接法:
链表是有序的,所以直接更改当前结点的 next 指针,跳过下一个结点并直接指向下一个结点之后的结点即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode *current=head; while(current!=NULL&¤t->next!=NULL) { while(current->next!=NULL&¤t->val==current->next->val) { current->next=current->next->next; } current=current->next; } return head;
} };
|
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
利用哑结点 :
为了防止删除头结点的极端情况发生,先创建空结点dummy,使dummy指向传入的head结点。
然后创建一个cur指针指向dummy,比较cur的后两个结点,看他们是否相同。
如果相同,则说明cur后有重复元素,此时创建一个temp指针指向第一个重复元素,即cur->next;
通过循环进行去重,循环结束后temp指向的是这群重复元素的最后一个,依照题意此时temp的下一个才是我们想要的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
|
class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode *dummy=new ListNode(-1); dummy->next=head; ListNode *cur=dummy;
while(cur->next!=NULL&&cur->next->next!=NULL) { if(cur->next->val==cur->next->next->val) { ListNode *temp=cur->next; while(temp->next!=NULL&&temp->val==temp->next->val) { temp=temp->next; } cur->next=temp->next; } else { cur=cur->next; } } return dummy->next; } };
|
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
双指针
如图,定义两个指针,pre在前 cur在后,temp 保存向前的pre指针的临时指针
每次进行一次局部翻转,
当pre到达尾部的时候终止,此时cur指向最后一个节点。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
class Solution { public: ListNode* reverseList(ListNode* head) {
ListNode *pre=head; ListNode *cur=NULL; ListNode *temp=NULL; while(pre!=NULL) { temp=pre; pre=pre->next; temp->next=cur; cur=temp; } return cur;
} };
|
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
| >输入: 1->2->3->4->5->NULL, m = 2, n = 4 >输出: 1->4->3->2->5->NULL
|
迭代法:
参考上题,先遍历到 m 处,再翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
class Solution { public: ListNode* reverseBetween(ListNode* head, int m, int n) { if(head==NULL) return NULL;
ListNode *pre,*cur; pre=head; cur=NULL; while(m>1) { cur=pre; pre=pre->next; m--; n--; }
ListNode*con=cur; ListNode*temp=NULL; ListNode*front=pre; while(n--) { temp=pre; pre=pre->next; temp->next=cur; cur=temp; } if(con!=NULL) { con->next=cur; } else { head=cur; } front->next=pre; return head; } };
|
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
迭代法:
直接连接各个节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
|
class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy=new ListNode(-1); ListNode *cur=dummy; while(l1!=NULL&&l2!=NULL) { if(l1->val>l2->val) { cur->next=l2; cur=cur->next; l2=l2->next; } else { cur->next=l1; cur=cur->next; l1=l1->next; }
} if(l1!=NULL) { cur->next=l1; } if(l2!=NULL) { cur->next=l2; } return dummy->next;
} };
|
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
当头节点不确定的时候,使用哑巴节点
将大于 x 的节点,放到另外一个链表,最后连接这两个链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
|
class Solution { public: ListNode* partition(ListNode* head, int x) { if(head==NULL) return head; ListNode *headDummy=new ListNode(-1); ListNode *tailDummy=new ListNode(-1); ListNode *cur=NULL,*tail=tailDummy; headDummy->next=head; head=headDummy; while(head->next!=NULL) { if(head->next->val<x) { head=head->next; } else { cur=head->next; head->next=head->next->next; tail->next=cur; tail=tail->next;
} } tail->next=NULL; head->next=tailDummy->next; return headDummy->next;
} };
|
给定一个带有头结点 head
的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
|
class Solution { public: ListNode* middleNode(ListNode* head) { ListNode *slow,*fast; slow=head; fast=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow;
} };
|
总结:如果链表长度是偶数,返回中间偏右的位置
且fast如果初始化为head->next 返回中间偏左的位置。
奇数长度则两者相同。
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
递归
归并排序链表,找中点和合并操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87
|
class Solution { public: ListNode* sortList(ListNode* head) { return mergeSort(head);
} ListNode *findMiddle(ListNode *head) { ListNode *slow,*fast; slow=head; fast=head->next; while(fast!=NULL&&fast->next!=NULL)
{ slow=slow->next; fast=fast->next->next;
} return slow; } ListNode * mergeTwoLists(ListNode*left,ListNode*right) { ListNode *dummy=new ListNode(-1); ListNode *head=dummy; while(left!=NULL&&right!=NULL) { if(left->val>right->val) { head->next=right; right=right->next; } else { head->next=left; left=left->next; } head=head->next; } while(left!=NULL) { head->next=left; head=head->next; left=left->next; } while(right!=NULL) { head->next=right; head=head->next; right=right->next; } return dummy->next; } ListNode *mergeSort(ListNode *head) { if(head==NULL||head->next==NULL) { return head; }
ListNode *middle=findMiddle(head);
ListNode* tail=middle->next; middle->next=NULL; ListNode *left=mergeSort(head); ListNode *right=mergeSort(tail); ListNode *res=mergeTwoLists(left, right); return res; } };
|
给定一个单链表 L:L0→L1→…→Ln-1→Ln ,
将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
此题目为2019年计算机统考408真题
思路:找到中点断开,翻转后面部分,然后合并前后两个链表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
|
class Solution { public: ListNode * findMiddle(ListNode *head) { ListNode *slow,*fast; slow=head; fast=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; } return slow;
} ListNode * mergeTwoLists(ListNode* l1,ListNode*l2) { ListNode* dummy=new ListNode(-1); bool toggle =true; ListNode *head=dummy; while(l1!=NULL&&l2!=NULL) { if(toggle) { head->next=l1; l1=l1->next; } else { head->next=l2; l2=l2->next; } toggle=!toggle; head=head->next; } while(l1!=NULL) { head->next=l1; l1=l1->next; head=head->next;
} while(l2!=NULL) { head->next=l2; l2=l2->next; head=head->next;
} return dummy->next; } void reorderList(ListNode* head) { if(head==NULL||head->next==NULL) return ; ListNode *middle=findMiddle(head); ListNode *tail=middle->next; middle->next=NULL; ListNode *cur,*pre; pre=tail; cur=NULL; while(pre!=NULL) { ListNode *temp=pre; pre=pre->next; temp->next=cur; cur=temp; } tail=cur; head->next=mergeTwoLists(head,tail)->next; } };
|
给定一个链表,判断链表中是否有环。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:
输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:
输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

快慢指针即可,就像你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
|
class Solution { public: bool hasCycle(ListNode *head) { if(head==NULL) return false; ListNode *fast,*slow; slow=head; fast=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; } };
|
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
示例 :
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

。
Floyd 算法
你在操场跑步,操场有环,只要你和她速度不一样,你们总能与她相遇,如果是直线,她到了终点,你就再也追不上她。此题分为两个阶段,第一个阶段先用快慢指针测试是否有环,第二阶段慢指针回到头head,然后各自以相同速度前进,相遇点即为入环处(可以自己画图尝试)。严格的数学证明可参考leetcode官方题解。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
|
class Solution { public: ListNode *detectCycle(ListNode *head) { if(head==NULL) return NULL; ListNode *slow,*fast; slow=head; fast=head; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; if(slow==fast) { slow=head; while(slow!=fast) { slow=slow->next; fast=fast->next;
} return slow; } } return NULL; } };
|
请判断一个链表是否为回文链表。
示例 1:
示例 2:
先找到链表中点,然后后面的翻转链表,一个个比较。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
|
class Solution { public: bool isPalindrome(ListNode* head) { if(head==NULL||head->next==NULL) return true; ListNode *slow,*fast; slow=head; fast=head->next; while(fast!=NULL&&fast->next!=NULL) { slow=slow->next; fast=fast->next->next; }
ListNode *cur,*pre,*tail,*temp; tail=slow->next; slow->next=NULL; pre=tail; cur=NULL; while(pre!=NULL) { temp=pre; pre=pre->next; temp->next=cur; cur=temp; } tail=cur;
while(head!=NULL&&tail!=NULL) { if(tail->val!=head->val) { return false; } head=head->next; tail=tail->next;
} return true;
} };
|
给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示:
val:一个表示 Node.val 的整数。
random_index:随机指针指向的节点索引(范围从 0 到 n-1);如果不指向任何节点,则为 null 。
复制节点跟在原节点后面即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
|
class Solution { public: Node* copyRandomList(Node* head) { if(head==NULL) return head; auto cur=head; while(cur!=NULL) { auto clone=new Node(cur->val); clone->next=cur->next; clone->random=cur->random; cur->next=clone; cur=clone->next; } cur=head; while(cur!=NULL) { if(cur->random!=NULL) { cur->next->random=cur->random->next; } cur=cur->next->next; } cur=head; auto cloneHead=cur->next; while(cur!=NULL&&cur->next!=NULL) { auto temp=cur->next; cur->next=cur->next->next; cur=temp; } return cloneHead; } };
|