算法解析001

2022-01-20

反转链表
查找链表环入口
爬楼梯
合并两个有序链表

反转链表

问题：
将一个单链表的所有节点反转
代码示例：

struct ListNode* reverseList(struct ListNode* head){
    struct ListNode* temp = NULL;
    struct ListNode* curr = head;
    while (curr) {
        struct ListNode* next = curr->next;
        curr->next = temp;
        temp = curr;
        curr = next;
    }
    return temp;
}

解题思路：
思路很简单，创建一个临时节点，挨个反转节点之间的关系，临时头结点为temp，每次移动temp和curr即可

查找链表环入口

问题：
查找一个链表中是否存在环，如果没有环，返回空；如果存在环，返回环入口结点；

代码示例：

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fast, *slow;
    fast = head;
    slow = head;
    while (true) {
        if (!fast || !fast->next) {
            return nil;
        }
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow) {
            break;
        }
    }
    fast = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
     return fast;
}

解题思路：
采用双指针差速法，通过求未知数公式求得：
设两指针 fast，slow 指向链表头部 head，fast 每轮走2 步，slow 每轮走1步；
第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；
TIPS: 若有环，两指针一定会相遇。因为每走1轮，fast 与 slow 的间距+1，fast 终会追上 slow；
第二种结果：当fast == slow时，两指针在环中第一次相遇。
下面分析此时fast 与 slow走过的步数关系：
设链表共有a+b 个节点，其中链表头部到链表入口有a个节点，链表环有b个节点。这里需要注意，a和b是未知数；接下来就是两个找出两个公式，求出这两个未知数。
设两指针分别走了f,s 步，则有：fast 走的步数是slow步数的2倍，即f=2s；
fast 比 slow多走了n 个环的长度，即f=s+nb；
以上两式相减得：f=2nb，s=nb，即fast和slow指针分别走了2n和n个环的周长。
如果要求链表环入口结点的位置，那么：
让指针从链表头部一直向前走并统计步数k，那么所有走到链表入口节点时的步数是：k=a+nb（先走a 步到入口节点，之后每绕1 圈环（b 步）都会再次到入口节点）。而目前，slow指针走过的步数为nb 步。因此，我们只要想办法让 slow 再走a步停下来，就可以到环的入口。而这个时候，让一个指针从head开始和slow的速度一样，走a步，正好会和走到链表环入口的slow指针相遇。此时相遇的位置即是链表环入口

爬楼梯

题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
代码示例：

int climbStairs(int n) {
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i) {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}

解题思路：
这个题解题要点在这句话”每次你可以爬 1 或 2 个台阶“，即第五阶台阶的方法数等于第三阶台阶再走两步的方法数加上第四阶台阶再走一步的方法数，即第五台阶的方法数等于第四台阶的方法数加第三台阶的方法数，那么这个问题也就变成了求斐波那契数列

合并两个有序链表

题目：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
代码示例：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode node1;
    node1.val = 0;

    struct ListNode* pList1 = list1;
    struct ListNode* pList2 = list2;
    struct ListNode* preHead = &node1;

    while (pList1 && pList2) {
        if (pList1->val < pList2->val) {
            preHead->next = pList1;
            pList1 = pList1->next;
        } else {
            preHead->next = pList2;
            pList2 = pList2->next;
        }
        preHead = preHead->next;
    }
    if (pList1) {
        preHead->next = pList1;
    } else {
        preHead->next = pList2;
    }
    return node1.next;
}

解题思路：
基本思路是，两个链表各取一个节点，比较大小，取小的节点接在最终链表上：
当两个链表都没到终点的时候，需要进行刚才的比较；当其中一个链表已经比较完毕，那么直接把剩下一个链表整体接在最终链表上即可。

链表相交

题目
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：

代码示例：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    if (headA == NULL || headB == NULL) {
        return NULL;
    }
    struct ListNode *pA = headA,*pB = headB;
    while (pA != pB) {
        pA = pA==NULL?headB:pA->next;
        pB = pB==NULL?headA:pB->next;
    }
    return pA;
}

解题思路：
这道题采用双指针法：
定义两个指针pA和pB，每步操作需要同时向后移动一个节点。
这时会有两个情况，一是，两者不相交，最终pA和pB都为NULL，返回NULL
一种是两者相交。
这时，如果pA等于NULL，让pA.next=pB,如果pB等于NULL，让pB.next=pA，依旧继续每次pA和pB都向后更新一个节点，直到pA和pB相等。
这个时候，算一个公式：
如上图假设，链表a，相交前的长度为a，相交后的长度为c；链表b，相交前的长度为b，相交后的长度为c。
这时，pA走过的长度为a+c+b;pB走过的长度为b+c+a；
去除掉各自链表本身的长度，每个指针都分别走过了对方链表前面不相交的长度，这个时候两者所在的节点就是相交点