【数据结构与算法】---OJ题库来源力扣牛客_好用的oj算法题

作者：旧梦拾遗186

专栏：数据结构成长日记

每日励志

有的人，一辈子只做两件事，不服，争取，所以越来越好。也有人，一辈子只做两件事，等待，后悔，所以越混越差。

目录

链表分割

描述

题解

 链表的回文结构 

描述

题解： 

相交链表 

---

链表分割

链表分割https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

题解

思路：我们给出两个带头结点的新链表，值小于X的放在第一条链表，值大于X的放在第二条链表，最后两个新链表连接起来即可。同时，我们需要注意到如果链表为空的时候，我们可以画个图：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* lessguard=(ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterguard=(ListNode*)malloc(sizeof(ListNode));
        ListNode* lesstail=lessguard;
        ListNode* greatertail=greaterguard;
        ListNode* cur=pHead;
        lessguard->next=NULL;
        greaterguard->next=NULL;
        while(cur)
        {
            if(cur->val<x)
            {
                lesstail->next=cur;
                lesstail=lesstail->next;
            }
            else
            {
                greatertail->next=cur;
                greatertail=greatertail->next;
            }
            cur=cur->next;
        }
        lesstail->next=greaterguard->next;
        greatertail->next=NULL;
        pHead=lessguard->next;
        free(lessguard);
        free(greaterguard);
        return pHead;
    }
};

 

 链表的回文结构 

 链表的回文结构https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

题解： 

思路：找到中间位置，进行后半段逆置，进行比对即可,到最后都为NULL。这其实就是找链表的中间结点以及反转链表的合集：

class PalindromeList {
public:
    //反转链表
      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*slow = head;
         struct ListNode*fast = head;
         while(fast&&fast->next)
         {
             slow = slow->next;
             fast = fast->next->next;
         }
         return slow;
 
}
 
    bool chkPalindrome(ListNode* head) {
        
        
         // write code here
        struct ListNode* mid = middleNode(head);
        struct ListNode* ret = reverseList(mid);
        //1 2 3 2 1
        //先反转中间以后的
        //1 2 1 2 3
        while (head && ret)
        {
            if (head->val == ret->val)
            {
                head = head->next;
                ret = ret->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
 
    
};

 

另一种解法：创建一个链表使之存放原链表的反转结果，然后在与原链表进行一一对比即可判断是否回文： 

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // write code here
        struct ListNode*cur = head;
        struct ListNode*newhead = NULL;
        struct ListNode*next = NULL;
        while(cur)
        {
            newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
            newhead->val = cur->val;
            newhead->next = next;
            next = newhead;
            cur = cur->next;
        }
        while(head)
        {
            if(newhead->val!=head->val)
            {
                return false;
            }
            else
            {
                newhead =newhead->next;
                head = head->next;
            }
        }
        return true;
     
    }
};

相交链表 

相交链表https://leetcode.cn/problems/intersection-of-two-linked-lists/

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

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。
 

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

题解：

思路：首先需要确定有没有相交，在于尾结点的地址是否相同

找交点——求出长度，既是LenA和LenB的长度。长链表先走差距步，后再同时走，第一个相等就是所求的交点,因为我们已经判断了是否相交。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* cur1=headA;
    struct ListNode* cur2=headB;
    int lenA=0;
    int lenB=0;
    while(cur1)
    {
        cur1=cur1->next;
        lenA++;
    }
    while(cur2)
    {
        cur2=cur2->next;
        lenB++;
    }
    if(cur1!=cur2)
    {
        return NULL;
    }
    struct ListNode* longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    int gap=abs(lenA-lenB);
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}