学习笔记，可能有些谬误，请批判性阅读。
先给出链表的定义。
class LinkNode{
public:
int val;
LinkNode* next;
LinkNode(int val){
val = val;
}
~LinkNode();
};
链表排序
归并排序用起来
LinkNode* merge(LinkNode* x, LinkNode* y){
if(x == NULL){
return y;
}
if(y == NULL){
return x;
}
LinkNode* rs = new LinkNode(-1);
LinkNode* head = rs;
LinkNode* p = x;
LinkNode* q = y;
while(p != NULL && q != NULL){
if(p->value <= q->value){
rs->mext = p;
}else{
rs->next = q;
}
}
if(p != NULL){
rs->next = p;
}
if(q != NULL){
rs->next = q;
}
return head->next;
}
LinkNode* sort(LinkNode* head){
if(head == NULL || head->next == NULL){
return head;
}
LinkNode* slow, fast = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
}
LinkNode* mid = slow->next;
slow->next = NULL;
return merge(sort(head), sort(mid));
}
删除链表倒数第n个节点
双指针实现。双指针是数据结构中一个很重要的思路。快排也是借助了双指针。
这里加上辅助指针，实际上借用了三个指针。
void delete_back_n(LinkNode* head, int n){
LinkNode* fast, slow, help = head;
for(int i = 0; i < n-1; i++){
fast = fast->next;
}
if(fast == NULL){
return; //异常检测，链表长度小于n，无法执行删除操作，直接返回。
}
fast = fast->next;
slow = slow->next; //协助指针慢一步。
while(fast != NULL){
fast = fast->next;
slow = slow->next; //当fast到达队尾时，slow指向了倒数第n个节点。
help = help->next;
}
help->next = slow->next; //执行删除操作
}
合并两个有序列表
最典型的归并排序。与合并两个有序数组是一样的方法。
LinkNode* merge_sorted_list(LinkNode* x, LinkNode* y){
LinkNode* dummy = new ListNode(-1);
LinkNode* p = x;
LinkNode* q = y;
LinkNode* real = dummy;
while(p != NULL && q != NULL){
if(p->val <= q->val){
dummy->next = p;
p = p->next;
}else{
dummy->next = q;
q = q->next;
}
dummy = dummy->next;
}
if(p != NULL){ // 把剩余的接上。
dummy->next = p;
}
if(q != NULL){
dummy->next = q;
}
return real->next;
}
判断链表中是否有环，若有，找到环的入口
第一阶段，判断是否有环，这已经是一个很经典的问题了。
思路还是双指针。
fast速度是slow的两倍。若有环，那么fast和slow终会相遇，也就是：
其中，是fast指针走过的距离，
是slow指针走过的距离。
是环的大小，上式表示两指针相遇时，fast指针比slow指针多走n圈。
bool has_cycle(LinkNode* head){
LinkNode* fast, slow = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return true;
}
}
return false;
}
第二阶段，若有环，找到环的入口。
做法是，当slow和fast相遇时，此时再有一个从head开始的指针finder，finder开始逐步走，slow保持逐步走，当两者相遇时，找到了环的入口。
需要证明一下。（此时就会意识到计算机就是数学）
- 假设head到环入口距离为
，环入口到slow&fast相遇节点的距离为
，slow&fast相遇时，fast多走了n圈：
- 因此，
- 此时，finder从head出发，与slow速度一致， 各自走
finder走过的距离：
slow走过的距离：
可以看到slow走过的距离比finder多圈，两者相遇了。
另一种解释：当finder从头出发走了a步时到达了环入口，此时slow从离环距离为圈，重新回到
LinkNode* has_cycle(LinkNode* head){
LinkNode* fast, slow, finder = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
while(slow != finder){
slow = slow->next;
finder = finder->next;
}
return finder;
}
}
}
判断一个链表是否为回文链表
需要一个辅助链表，就是原链表的翻转。然后再进行比较。
两数相加
用链表存储两个数，计算两个数之和，结果也用链表存储。
例如，用链表表达：
，加上
，结果为
。
这个问题实际需要考虑的是进位问题。由于已经是从低位到高位存储了，直接顺序计算即可。
LinkNode* add(LinkNode* x, LinkNode* y){
LinkNode* p = x;
LinkNode* q = y;
LinkNode* dummy = new LinkNode(-1);
LinkNode* real = dummy;
int carry = 0;
while(p != NULL || q != NULL){
int sum = carry;
if(p != NULL){
sum += p->val;
p = p->next;
}
if(q != NULL){
sum += q->val;
q = q->next;
}
cur = sum % 10;
carry = sum / 10; //进位
dummy->next = new LinkNode(cur);
dummy = dummy->next;
}
if(carry > 0){ // 若最后还有进位，位数增加。
dummy->next = new LinkNode(carry);
}
return real->next;
}
求两个链表的交点
思路很直观，先求两个链表的长度，然后两个指针分别出发，较长的链表先走长出的步数。两个指针相遇之处就是交点。
LinkNode* find_intersection(LinkNode* x, LinkNode* y){
int len_x, len_y = 0;
LinkNode* p = x;
LinkNode* q = y;
while(p != NULL){
p = p->next;
++len_x;
}
while(q != NULL){
q = q->next;
++len_y;
}
p = x; //回到head
q = y;
if(len_x > len_y){ //指向较长链表的指针先走
for(int i = 0; i < len_x - len_y; i++){
p = p->next;
}
}else if(len_x < len_y){
for(int i = 0; i < len_y - len_x; i++){
q = q->next;
}
}
while(p != NULL && q != NULL && p != q){
p = p->next;
q = q->next;
}
if(p != NULL && q != NULL){ //若p&q都不为空，表示找到了交点。
return p;
}
//否则没有交点
}
有序数组/链表转换为BST
BST是二叉查找树，这个问题和算法无关，纯粹的数据结构。
有序数组转换为BST的情况，需要给出子序列的头尾。
TreeNode* transfer(int* a, int n){
if(n == 0){
return;
}
return helper(a, 0, n - 1);
}
TreeNode* helper(int* a, int start, int end){
if(start >= end){
return;
}
int mid = (start + end) / 2;
TreeNode* root = new TreeNode(a[mid]);
root->left = helper(a, start, mid -1);
root->right = helper(a, mid + 1, end);
return root;
}
有序链表的话，需要双指针，fast & slow，先找到链表中间的那个节点。
TreeNode* transfer(LinkNode* head){
if(head == NULL){
return;
}
TreeNode fast, slow = head;
while(fast != NULL && fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
}
TreeNode* root = new TreeNode(slow->val);
root->left = transfer(head);
root->right = transfer(slow->next);
return root;
}
先到这里吧。
网友评论