学会了链表还不赶紧来刷题《二》

---

回文链表题目分析：

代码实现：

相交链表的题目分析：

代码实现：

思路一：

思路2：（浪漫又难理解）

环形链表的题目分析：

代码实现：

环形链表 || 的题目解析：

代码实现：

思路1：（示意图如下）

思路2：（示意图如下）

复制带随机指针的链表题目分析：

代码实现：

---

昨天我们看的是链表比较基础的题，今天我们来看下比较新颖的题。

234. 回文链表

回文链表题目分析：

这道题我们看起来比较简单，就是判断是不是回文，我们用的答题思路是：

先找到链表的中间节点，

然后从中间节点向后的链表逆置，

最后两个，一个头指针，一个中间节点的指针，向后遍历，为空停止。

示意图如下：

代码实现：

首先我们找中间节点，然后逆置，这都已经学过了。

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* Newnode = NULL;
    struct ListNode* cur = head;

    while(cur)
    {
        struct ListNode *tmp = cur->next;
        cur->next = Newnode;
        Newnode = cur;
        cur = tmp;
    }

    return Newnode;
}

struct ListNode* middleNode(struct ListNode*head)
{
    struct ListNode* fast = NULL;
    struct ListNode* slow = NULL;
    fast = slow = head;

    while(fast->next && fast->next->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

bool isPalindrome(struct ListNode* head)
{
    struct ListNode* mid = middleNode(head);
    struct ListNode* rhead = reverseList(mid);

    while(rhead && head)
    {
        if(rhead->val != head->val)
        {
            return false;
        }
        else
        {      
            rhead = rhead->next;
            head = head->next;
        }
    }

    return true;
}

1.首先找中间节点。

2.逆置中间节点到最后的结点之间的链表。

3.两个指针一个指向头指针，一个指向中间节点的指针，进行遍历，任何一个结点为空停止。

注意：结点数奇数和偶数都是适用的，我们可以通过上述示意图看出，我们还是注意循环的结束条件，我们想的是结束条件，但是写在循环的限定条件处的是继续条件。

160. 相交链表

相交链表的题目分析：

 我们看到这个题目样式比较简单，就是两个链表求交点，并且为无环链表，思路如下：

思路一：我们可以算出链表长度，求差值，然后让长的链表先走，然后在一起走，如果相等就返回。

思路二（浪漫又抽象）：定义两个指针，一个先走长链表，再走短链表，一个先走短链表，再走长链表，最后会在交点处相遇。

（你走过我走的路，我们最终会相遇，愿天下有情人都返回 true ）

思路三：我们可以把其中一个链表链接起来，变成判断链表带环问题（自己实现哦）

代码实现：

思路一：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    int lenA = 1, lenB = 1;
    struct ListNode* curA = headA, *curB = headB;
    //计算链表长度
    while(curA)
    {
        ++lenA;
        curA = curA->next;
    }
    
    while(curB) 
    {
        ++lenB;
        curB = curB->next;
    }
    

    int gap = abs(lenA-lenB);
    struct ListNode* longList = headA, *shortList = headB;
    if(lenA < lenB)//假设法，得到长链表
    {
        longList = headB;
        shortList = headA;
    }
    //让长链表先走几步
    while(gap--)
    {
        longList = longList->next;
    }


    //两个链表同时走，直到遇到相同的节点
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            return longList;
        }
        else 
        {
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    
    return NULL;
}

1.首先我们先遍历一遍链表，得到两个链表的长度。

2.算出两个链表的差值。

3.使用假设法，求出链表中较长的，然后让长链表走差值步。

4.让两个链表同时走，节点值相等就返回节点，不相等返回NULL，说明没交点。

注意：思路一虽然思想简单，但是实现的过程中很多细节需要注意，比如假设法求较长的链表，比如循环结束条件。

思路2：（浪漫又难理解）

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    struct ListNode *pA = headA;
    struct ListNode *pB = headB;

    if(headA == NULL  || headB == NULL)
    {
        return NULL;
    }

    while(pA != pB)
    {
        pA = pA == NULL ? headB : pA->next;
        pB = pB == NULL ? headA : pB->next;
    }    

    return pA;
}

我们看上述图示来理解，就会方面很多了。

 

注意：我们先要判断这两个链表都要不为空，并且在一个链表走到NULL时，要直接走下一个链表。 

141. 环形链表

环形链表的题目分析：

我们依然可以使用快慢指针追赶的形式来进行解答，快指针一次走2步，慢指针一次走一步，然后快指针先入环，然后慢指针在入环，然后让快慢指针再环内追赶，最后相遇。 

代码实现：

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow)
        {
            return true;
        }
    }

    return false;
}

代码上没什么难点，我们要注意循环的限定条件是快指针为空或者快指针的next为空。

为什么要走两步呢？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情 况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

必须快指针走2步才可以，走3步可以吗？

142. 环形链表 II

环形链表 || 的题目解析：

这个题目实际上要我们返回链表的入环点，如果没环就返回NULL。

 

这个题的整体思路是先用快慢指针判断是否链表有环，然后顺带求出快慢指针在环的相遇点，接着我们就分为两种思路：

思路一：

我们把相遇节点保存，在保存它的下一个节点，然后从相遇节点断开，问题转化为求两个链表的相交，求交点。

思路二：我们把相遇点保存，然后遍历，让头结点，和相遇点同时向前走，最后会在入环点相遇。

代码实现：

思路1：（示意图如下）

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;    
    struct ListNode* slow = head;
    while(fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            struct ListNode* phead = fast->next;
            struct ListNode* p1 = phead;
            struct ListNode* p2 = head;
            fast->next = NULL;
            while(p1 != p2)
            {
                p1 = p1 == NULL? head: p1->next;
                p2 = p2 == NULL? phead: p2->next;
            }
            return p1;
        }
    }   

    return NULL;
}

1.先求相遇点。

2.保存相遇点的next。

3.求两个链表相交。

思路2：（示意图如下）

 

 我们根据上图的逻辑，以及结论是可以写出思路二的代码的。

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

        if(fast == slow)
        {
            struct ListNode* meet = fast;
            
            while(head != meet)
            {
                meet = meet->next;
                head = head->next;
            }

            return meet;

        }
    } 
    return NULL;    
}

138. 复制带随机指针的链表

复制带随机指针的链表题目分析：

这道题也叫做链表的深拷贝，就是有一个链表，他有两个指针，一个指向随机值，一个指向下一个，要求我们拷贝一份这样的链表。 

我们的答题思路是，先在创建每个节点，链接到原节点的后面，然后它的随机指针就是源节点的随机指针的next，然后把拷贝的节点尾插就好啦。

代码实现：

 

struct Node* copyRandomList(struct Node* head) 
{
    struct Node* cur = head;

    while(cur)//创建结点链接到后面
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;

        copy->next = cur->next;
        cur->next = copy;

        cur = copy->next;
    }	

    cur = head;

    //链接随机指针 copy->random = cur->random->next
    while(cur)
    {
        struct Node* copy = cur->next;

        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }

        cur = copy->next;
    }

    cur = head;
    //尾插
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;

    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;

        if(copytail == NULL)
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }

        cur->next = next;
        cur = next;
    }

    return copyhead;
}

1.先创建节点，链接到原链表每个节点的后面。

2.然后就是 copy->random = cur->random->next 的理解到位，如果原节点的 random 指为NULL，则 copy->random 也指为 NULL。

3.把 copy 的节点拿下来尾插一个新链表，返回就可以啦。

我们最重要的是明白 copy->random = cur->random->next，这个的由来。