结构|链表

作者: 紫色de枫 | 来源:发表于2019-12-21 20:47 被阅读0次

数据结构——线性表
链表基础
数据结构-链表
线性表--链式存储结构--双向链表
链表
C语言数据结构-链表大解剖
算法与数据结构知识汇总（二、链表）
iOS 数据结构之链表
数据结构 | 其二链表
js+链表

学习笔记，可能有些谬误，请批判性阅读。

先给出链表的定义。

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终会相遇，也就是：
$d1-d2=n*r$
其中， $d1$ 是fast指针走过的距离， $d2$ 是slow指针走过的距离。 $r$ 是环的大小，上式表示两指针相遇时，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到环入口距离为 $a$ ，环入口到slow&fast相遇节点的距离为 $x$ ，slow&fast相遇时，fast多走了n圈： $a+x+(n+m)r=2(a+x+mr)$
因此， $a=(n-m)r-x$
此时，finder从head出发，与slow速度一致，各自走 $a$ 步。
finder走过的距离： $(n-m)r-x$
slow走过的距离：
$a+x+(n+m)r+a$
$=2a+x+(n-m)r$
$=2((n-m)r-x)+x+(n-m)r$
$=3(n-m)r-x$
可以看到slow走过的距离比finder多 $2(n-m)$ 圈，两者相遇了。
另一种解释：当finder从头出发走了a步时到达了环入口，此时slow从离环距离为 $x$ 的位置出发，那么就相当于又走了 $(n-m)$ 圈，重新回到 $x$ 位置，加上还需要回退x步，也就是回到了环入口。

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;
        }
    }
}

判断一个链表是否为回文链表

需要一个辅助链表，就是原链表的翻转。然后再进行比较。

两数相加

用链表存储两个数，计算两个数之和，结果也用链表存储。
例如 $123+458=581$ ，用链表表达： $3\rightarrow 2\rightarrow 1$ ，加上 $8\rightarrow 5\rightarrow 4$ ，结果为 $1\rightarrow 8\rightarrow 5$ 。

这个问题实际需要考虑的是进位问题。由于已经是从低位到高位存储了，直接顺序计算即可。

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;
}

先到这里吧。