数据结构每日亿题(二)

文章目录

一.链表的中间结点

原题传送门：

力扣

题目：

在这里插入图片描述

这题可以有两种方法，第一种比较暴力，就是很容易想到。

1.1暴力破解

不管后面怎么样写，先把链表遍历一遍，计算出链表有多少个元素，然后/2，这样再来个循环把中间节点找出来，这样写的话时间复杂度是O(N)，空间复杂度是O(1).

	//定义一个变量来计算链表元素的个数
	int count = 0;
	
	//定义一个结构体变量，指向链表头节点
    struct ListNode* cur;
    cur = head;

	//用while循环来计算
    while(cur)
    {
        cur = cur->next;
        count++;
    }

接下来我们来分两种情况来判断：

链表个数是奇数个：

1，2，3，4，5.这样计算的count是5。然后5/2 = 2.
链表个数是偶数个：

1，2，3，4.这样计算的count是4。但是4/2的结果仍然是2.

也就是说，不论链表的个数是奇数个，还是偶数个，要找的都是一个节点。

//将count除2
count /= 2;

//这里我们将cur重新指向头节点，一会我们还用它来遍历链表
cur = head;

我们发现链表个数是5，4的时候count的值都是2，所以可以认为要从头开始遍历，要往后走三步，才能找到想要的节点

    for(int i = 0; i < count; i++)
    {
        cur = cur->next;
    }

这样cur指向的就是我们需要的中间节点了，最后返回cur就行。

1.2快慢指针

接下来，我再来教一种神奇的算法：快慢指针。

题目是要求我们找到中间节点，如果我们希望有一个指针指向了一个链表中间的位置，麻烦的是我们不知道这个中间节点在哪。

但是如果我们还有一个指针它走的比刚才那个指针走的快，并且速度是它的两倍，这样的话这个快指针走到链表末尾的时候，刚才那个指针是不是刚好走到了这个链表的中间位置。

这样思路就出来了，而且我们需要把这些步骤放在一个循环了。然后我们同样要分两种情况：

在这里插入图片描述

这个快指针fast两步两步的走，走两次之后是不是就走到链表最后一个节点了，而且满指针slow也正好走到了链表的中间位置。现在就可以推算出循环的终止条件是：

while(fast->next != NULL)

当个数是偶数时：

在这里插入图片描述

同样是要走两步才可以找到中间节点，但是此时的fast已经指向了NULL，所以这时候循环的终止条件也可以写出来了：

while(fast != NULL)

但是我们不知道这个链表个数是偶数还是奇数，所以我们把循环条件合在一起：

while(fast != NULL && fast->next != NULL)
//当然这样写也可以
while(fast && fast->next)

这里有一个小细节，while循环里你不能把fast->next写在fast前面。像这样：

while(fast->next != NULL && fast != NULL)

如果这个链表长度是奇数个还好说，但是如果是偶数个呢？那快指针最后结束的时候必然指向的是

空指针

，但我们这里毕竟是while循环呀，你变成空指针之后还要再到while条件里判断一下才能退出去，但此时循环里的判断有一个

先后顺序

，也就是先判断fast->next是否为空，但是这时候就出现问题了，fast指针已经是空了，你还要强行对它解引用这不就出现问题了么。

所以在写的时候将fast != NULL写在前面，当fast为空时就直接跳出循环不用判断后面了，也就不存在解引用空指针的情况了。

最后的代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


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

    if(head == NULL)
    {
        return NULL;
    }

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

二.链表中倒数第k个结点

原题传送门：

牛客网

题目：

在这里插入图片描述

当然这题也有比较暴力的解法，如果找倒数第k个数就定义一个指针，总共往后走n-k步(n是节点的个数)。这里就不细说了，因为今天的主要知识点是

快慢指

针。

经过了第一题的磨练，我们有了一点点思路，就是首先需要一个慢指针，结束时它指向的位置是我们想要的位置，我们还要一个快指针，来判断我们什么时候结束。

假设一个链表是1->2->3->4->5有5个节点，而我们需要找到倒是第1个节点：

在这里插入图片描述

那我们快指针此时可以指向什么位置呢？我们有两种选择：

我们可以判断fast是否为空，如果为空就停止循环
可以判断fast->next是否为空，如果为空就停止循环

但是我们一般喜欢用第一种方式判断：

while(fast != NULL)

因为如果使用第二种，我们还要多加一个if判断，如果链表为空，我们还要判断fast->next这就会造成空指针解引用问题。

好，思路已经出来一半了，如果想得到倒数第一个节点，此时两个指针的位置：

在这里插入图片描述

如果想要倒数第二个节点的位置呢？

再看倒第三个：

通过这三组，规律是不是已经找到了，如果想要找到倒数第一个节点，fast指针要比slow指针多走一步，倒数第二个节点是多走两步…

我们就可以这样写：先让fast指针走k步，走完之后两个指针在同时走，指定fast指针为空结束，此时slow指向的节点就是答案：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    // write code here
    struct ListNode* slow = pListHead;
    struct ListNode* fast = pListHead;

    while(k--)
    {
        if(fast == NULL)
        {
            return NULL;
        }
        fast = fast->next;
    }
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

三.链表的回文结构

原题传送门：

牛客网

题目：

在这里插入图片描述

回文结构是正着看和反着看是一样的。

这题看上去比较难，但是仔细分析一下也还是很简单的。

我们肯定要分两种情况来讨论：

节点数是偶数个如1->2->2->1
节点数是奇数个如1->2->3->2->1

如果它是顺序表，应该很快就能写出来，两个指针一前一后往中间遍历就行，但是这是单链表，你指针做不到从后向前这种动作。

但是我们可以这样：

找到链表的中间位置，将链表分成两半
把后一半链表翻转过来
然后定义两个指针，分别指向这两部分的其实节点

这样我们就把问题简化了。首先找到链表中间位置应该不难吧，第一题就是的。

如果是1->2->2->1就应该反转这一部分：

在这里插入图片描述

如果是1->2->3->2->1,应该反转的是这一部分：

第二步是翻转，这一步我在

数据结构每日一题(一)

里提到过。

主要思路是定义两个指针phead:

在这里插入图片描述

然后我们把链表里的3->2->1一个一个的拿下来，前插：

在这里插入图片描述

然后没拿下来一个，phead指针都要更新一下位置，指向新节点的位置。

这样我们把链表的逆序也做好了：

这样我们定义两个新的变量分别指向两个链表的其实位置：

在这里插入图片描述

如果之前的链表节点数是偶数应该好判断：

一直循环，知道p2为空，如果此时两个指针的值都一样就说明是回文函数，如果有一个不相等，就不是回文结构。

但是奇数个怎么判断呢？

在这里插入图片描述
其实画下图也能看得出来，当p2指向3这个节点的时候，p1此时指向哪里？

我们看之前的节点2，此时他应该指向的是节点3.这应该没问题吧。虽然后来我们把3，2，1这些节点都倒过来了，但我们自始至终没变过2->next这个地址吧，是不是说，最后2这个节点指向的还是三这个节点？

在这里插入图片描述
这样就能理解清楚了吧，p2运动的轨迹是1->2->3->NULL,p1的运动轨迹也是1->2->3->NULL.所以也可以判断出这是一个回文结构。

具体代码实现：

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/

//这是逆置链表的函数
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* newhead = NULL;
    struct ListNode* cur = head;

    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

//这是找中间节点的函数
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    if(head == NULL)
    {
        return NULL;
    }

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


class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here

        //先找中间节点,用middle指针接收
        ListNode* middle = middleNode(A);

        //逆置链表,用rever指针接收
        ListNode* rever = reverseList(middle);

        //定义一个指针cur指向头指针
        ListNode* cur = A;

        //循环判断，直到rever为空
        while(rever)
        {
            //如果在判断中有一个不一样就说明它不是回文结构
            if(rever->val != cur->val)
            {
                return false;
            }
            rever = rever->next;
            cur = cur->next;
        }

        //走到这里说明遍历完了
        return true;
    }
};

这里主函数那里用的是C++的写法(因为牛客网这题没有C语言的写法)，如果不熟悉也没关系，函数的内容和C语言是一样的，你忽略那两行看不懂的就行。

这里逆置函数，找中间节点的函数之前已经写过了，现在就是直接拿过来用。

四.相交链表

原题传送门：

力扣

题目：

在这里插入图片描述

题目意思简单一点说就是，给你两个链表，判断这两个链表有没有节点的地址是一样的，如果有我们现在需要找到这个节点，如果没有就返回NULL。

首先想到的第一种暴力的方法是遍历，先判断第二个链表的所有节点看看地址是否和第一个链表的第一个地址相等…但这种想法基本可以放弃了，因为时间复杂度是O(N^2).

但是，这一题我们还可以用快慢两个指针来进行操作。

我们看这个例子：

在这里插入图片描述

如果两个链表分别从头开始遍历：

第一个链表指针走向：1->9->1->2->4->NULL

第二个链表指针走向：3->2->4->NULL

发现本来在节点2那里就可以找到交点了，但是通过上面的顺序发现，这样根本行不通。所以我们现在需要的两个指针的其实位置是：

在这里插入图片描述

就是希望长链表的指针要提前走X步，这样fast,slow指针就可以同时向后遍历了，如果有地址是一样的时候就可以返回该节点，没有就返回NULL。

但是X要怎么找呢？仔细通过图可以看到，fast指针多走的步数应该是长链表的节点个数减去短链表的，所以在计算X之前，要先把两个链表的大小算出来：

    int lenA = 0;
    int lenB = 0;

    //随便定义两个指针，因为此时还不知道哪个长哪个短
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;

    //计算链表的大小
    while (curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while (curB->next)
    {
        curB = curB->next;
        lenB++;
    }

lenA,lenB已经计算出来了，但是仔细看代码会发现curA,curB两个指针分别指向的是两个链表的最后一个节点。那现在是不是可以直接判断这两个链表有没有交叉点。因为如果最后一个节点都不一样的话，就说明这两个链表没有交叉点，此时直接返回NULL：

//此时curA,curB指向链表末尾，如果两者地址不相等说明没有交点
    if (curA != curB)
        return NULL;

现在我们要判断快指针指向哪个链表，慢指针指向哪个链表：

    //计算两个数差值的绝对值，也就是快指针该走的步数
    int absoulte = abs(lenA - lenB);

    //随便定义两个指针，因为此时还不知道哪个长哪个短
    struct ListNode* fast = headA;
    struct ListNode* slow = headB;

    //假设headA比headB要长，如果猜错了就换一下位置
    if (lenA < lenB)
    {
        fast = headB;
        slow = headA;
    }

计算好之后，我们就可以提前让快指针先走了：

    //此时将快指针先走absoulte步
    while (absoulte--)
    {
        fast = fast->next;
    }

最后我们再来遍历两个指针：

因为刚才已经把没有交点的那种情况已经解决掉了，如果程序走到这里来，说明肯定有交点。

    //遍历
    while (fast != slow)
    {
        fast = fast->next;
        slow = slow->next;
    }
    //跳出循环说明交点已经找到了
    return fast;