刷爆leetcode第二期

简介: 刷爆leetcode第二期

题目一 分割链表

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。


你不需要 保留 每个分区中各节点的初始相对位置。


我们来看图

还是使用我们上期用过的哨兵位头节点容易做一点 刷爆leetcode第一期-CSDN博客

1.分别开辟两个哨兵位头节点lguard,Gguard,以及他们的尾节点ltail,Gtail,再定义一个cur指针指向原链表头指针,方便向后走

2.比较比x小的尾插到lguard链表中,反之则尾插到Gguard链表中,cur,ltail,Gtail,分别向后走

3.最后将Gguard尾插到lguard

4.将lguard和Gguard释放(不可忽略)

看代码:

struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
}; 
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lguard, * ltail, * Gguard, * Gtail;
        lguard = ltail = (struct ListNode*)malloc(sizeof(struct ListNode));
        Gguard = Gtail = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* cur = pHead;
        ltail->next = NULL;
        Gtail->next = NULL;
        while (cur)
        {
            if (cur->val < x)
            {
                ltail->next = cur;
                ltail = ltail->next;
            }
            else {
 
                Gtail->next = cur;
                Gtail = Gtail->next;
            }
            cur = cur->next;
        }
        ltail->next = Gguard->next;
        Gtail->next = NULL;
        pHead = lguard->next;
        free(lguard);
        free(Gguard);
        return pHead;
    }
};

注意一定要把哨兵位头节点释放


题目二 回文链表

给你一个单链表的头节点 head ,请你判断该链表是否为回文链表。如果是,返回 true ;否则,返回 false 。

看图

这道题就要用到我们上一期做题的思路刷爆leetcode第一期-CSDN博客

1.找到中间节点

2.从中间节点开始对后半段逆置

3.前半段和后半段比较就可以了

看代码:

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
 
//找到中间节点
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* slow = NULL, * fast = NULL;
    slow = fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
//逆置
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
        newhead = cur;//更新头节点
        cur = next;
 
    }
    return newhead;
}
class PalindromeList {
public:
    bool chkPalindrome(ListNode* head) {
        struct ListNode* mid = middleNode(head);
        struct ListNode* rhead = reverseList(mid);
        while (head && rhead)
        {
            if (head->val != rhead->val)
            {
                return false;
            }
            else
            {
                head = head->next;
                rhead = rhead->next;
 
            }
        }
        return true;
    }
};


题目三 双链表相交节点

输入两个链表,找出它们的第一个公共节点。

1.分别求俩个链表的长度

2.长的先走差距步

3.同时走,第一个地址相同就是交点

看代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* tailA = headA, * tailB = headB;
    int lenA = 1;
    int lenB = 1;
    //计算链表A的长度
    while (tailA->next)
    {
        tailA = tailA->next;
        ++lenA;
    }
    while (tailB->next)//B的长度
    {
        tailB = tailB->next;
        ++lenB;
    }
    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)
    {
        longlist = longlist->next;
        shortlist = shortlist->next;
    }
    return longlist;
 
}
目录
相关文章
|
5月前
刷爆leetcode第一期
刷爆leetcode第一期
23 1
|
5月前
|
索引
刷爆leetcode第四期
刷爆leetcode第四期
19 0
|
5月前
|
索引
刷爆leetcode第三期
刷爆leetcode第三期
25 0
|
5月前
|
测试技术 C语言
刷爆leetcode第五期
刷爆leetcode第五期
23 0
|
5月前
刷爆leetcode第七期
刷爆leetcode第七期
21 0
|
5月前
刷爆leetcode第六期
刷爆leetcode第六期
20 0
|
5月前
刷爆leetcode第八期
刷爆leetcode第八期
16 0
|
算法 测试技术
刷爆 LeetCode 双周赛 100,单方面宣布第一题最难
上周末是 LeetCode 第 100 场双周赛,你参加了吗?这场周赛整体没有 Hard 题,但是也没有 Easy 题。第一题国服前百名里超过一半人 wa,很少见。
124 0
|
存储
刷爆leetcode第二期 0002~0006
刷爆leetcode第二期 0002~0006
85 0
刷爆leetcode第二期 0002~0006
刷爆leetcode第七期 0018
刷爆leetcode第七期 0018
108 0
刷爆leetcode第七期 0018