链表高频笔试的OJ题

文章目录

一、合并两个有序链表

解题代码

二、反转链表

解题代码

三、分割链表

解题代码 

四、链表的回文结构

解题代码

五、链表相交

解题代码

六、环形链表

解题代码

七、复制带有随机指针的复制链表

解题代码

一、合并两个有序链表

题目来源：牛客网。

题目难度：简单。

题目描述：输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0 <= n <= 1000,-1000≤节点值≤1000，要求：空间复杂度 O(1)，时间复杂度 O(n）。

  题解关键思路：

1. 定义一个哨兵位，易方便操作；
2. 定义一个尾节点，插入时时刻改变尾节点，方便书写代码；
3. 比较数据大小，依次尾插即可；
4. 当有一个链表提前比较插入结束，不要忘记把另一个链表剩下的元素连接起来。

解题代码

struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) 
{
    if(pHead1==NULL)
    {
        return pHead2;
    }
    if(pHead2==NULL)
    {
        return pHead1;
    }
    struct ListNode* head,* tail;
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(pHead1&&pHead2)
    {
        if(pHead1->valval)
        {
            tail->next=pHead1;
            tail=pHead1;
            pHead1=pHead1->next;
        }
        else
        {
            tail->next=pHead2;
            tail=pHead2;
            pHead2=pHead2->next;
        }
    }  
    if(pHead1)
    {
        tail->next=pHead1;
    }
    if(pHead2)
    {
        tail->next=pHead2;
    }
    struct ListNode* plist=head->next;
    free(head);
    return plist;
}

二、反转链表

题目来源：牛客网。

题目难度：简单。

题目描述：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤1000

要求：空间复杂度 O(1) ，时间复杂度O(n) 。

  题解关键思路：

1. 反转next的指向即可；
2. 定义三个节点，分别指向空、首节点、第二个节点，从首节点开始反转，依次向后访问。
3. 也可考虑头插的思路，即定义一个新节点为空，把题目中的链表依次头插入新节点即可。 

解题代码

// struct ListNode* ReverseList(struct ListNode* pHead ) {
//     if (pHead == NULL)
//         return NULL;
//     struct ListNode* n1, *n2, *n3;
//     n1 = NULL;
//     n2 = pHead;
//     n3 = pHead->next;
//     while (n2) {
//         n2->next = n1;
//         n1 = n2;
//         n2 = n3;
//         if (n3)
//             n3 = n3->next;
//     }
//     return n1;
// }
struct ListNode* ReverseList(struct ListNode* pHead )
{
    if(pHead==NULL)
        return NULL;
    struct ListNode* newhead=NULL;
    struct ListNode* cur=pHead;
    struct ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        next=cur->next;
    }
    return newhead;
}

三、分割链表

题目来源：LeetCode。

题目难度：中等。

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

题解关键思路：

1. 定义两个新节点，把大于x的和小于x的分成两部分；
2. 最后连接两部分；
3. 注意，最后应该将最后一个节点的next置空，防止成回链。

解题代码 

struct ListNode* partition(struct ListNode* head, int x)
{
    struct ListNode* lesshead,*lesstail;
    lesshead=lesstail=(struct ListNode*) malloc(sizeof(struct ListNode));
    lesstail->next=NULL;
    struct ListNode* greaterhead,*greatertail;
    greaterhead=greatertail=(struct ListNode*)malloc(sizeof(struct ListNode));
    greatertail->next=NULL;
    struct ListNode* cur=head;
    while(cur)
    {
        if(cur->val
        {
            lesstail->next=cur;
            lesstail=cur;
        }
        else
        {
            greatertail->next=cur;
            greatertail=cur;
        }
        cur=cur->next;
    }
    lesstail->next=greaterhead->next;
    greatertail->next=NULL;
    struct ListNode* plist=lesshead->next;
    free(lesshead);
    free(greaterhead);
    return plist;
}

四、链表的回文结构

题目来源：LeetCode。

题目难度：简单。

题目描述：给定一个链表的 头节点 head ，请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

题解关键思路：

1. 第一步：找到前半部分尾结点(快慢指针)；
2. 第二步：翻转后半部分(翻转链表)；
3. 第三步：判断是否是回文链表(判断前后两部分的节点是否一致)；
4. 第四步：返回结果。

解题代码

 struct ListNode* Reverse(struct ListNode* head)
 {
    struct ListNode* head1=head;
    struct ListNode *n1,*n2,*n3;
    n1=NULL;
    n2=head1;
    n3=head1->next;
    while(n2)
    {
        n2->next=n1;
        n1=n2;
        n2=n3;
        if(n3)
        n3=n3->next;
    }
    return n1;
 }
bool isPalindrome(struct ListNode* head)
{
    if(head==NULL||head->next==NULL)
    {
        return true;
    }
    struct ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    struct ListNode*headRev=Reverse(slow);
    struct ListNode*headBef=head;
    while(headBef&&headRev)
    {
        if(headBef->val!=headRev->val)
        {
            return false;
        }
        else
        {
            headBef=headBef->next;
            headRev=headRev->next;
        }
    }
    return true;
}

五、链表相交

题目来源：LeetCode。

题目难度：简单。

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

题解关键思路：

1.  指针 curA 指向 A 链表，指针 curB 指向 B 链表，依次往后遍历；

2.  先判断curA 和curB的尾是否相同，如果相同，则交叉，如果不同，则不交叉；

3. 统计两个链表的节点数来判断谁长谁短；

4. 从头遍历，比较长的链表指针先走两者之差，长度差就消除了如此，再依次同时往后遍历找相同即可。

解题代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int countA=1;
    int countB=1;
    while(curA->next||curB->next)
    {
        if(curA->next)
        {
            curA=curA->next;
            countA++;
        }
        if(curB->next)
        {
            curB=curB->next;
            countB++;
        }
    }
    if(curA!=curB)
    {
        return NULL;
    }
    int gap=abs(countA-countB);
    struct ListNode* longlist=headA;
    struct ListNode* shortlist=headB;
    if(countA
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
    {
        longlist=longlist->next;
    }
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}

六、环形链表

题目来源：LeetCode。

题目难度：中等。

题目描述：给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。

  

题解关键思路：

1. 先判断是否为环形链表（快慢指针）；
2. 是环形链表后，找入环点；
3. 找入环点的方法：一个指针从相遇点开始，另个一指针从头开始，当两个指针相等时即为入环点。 

解题代码

struct ListNode *detectCycle(struct ListNode *head)
{
    struct ListNode *slow=head,*fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            struct ListNode *meet=fast;
            while(meet!=head)
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return NULL;
}

七、复制带有随机指针的链表

题目来源：LeetCode。

题目难度：中等。

题目描述：给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。返回复制链表的头节点

  

题解关键思路：

1. 首先我们可以忽略 random 指针，然后对原链表的每个节点进行复制，并追加到原节点的后面，而后复制 random 指针。

2. 最后我们把原链表和复制链表拆分出来，并将原链表复原即可。

解题代码

struct Node* copyRandomList(struct Node* head)
{
    struct Node* cur=head;
    //插入相同的节点
    while(cur)
    {
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        newnode->val=cur->val;
        //插入节点
        newnode->next=cur->next;
        cur->next=newnode;
        cur=newnode->next;
    }
    //复制随机指针
    cur=head;
    while(cur)
    {
        if(cur->random==NULL)
        {
            cur->next->random=NULL;
        }
        else
        {
            cur->next->random=cur->random->next;
        }
        cur=cur->next->next;
    }
    //拆解插入的指针
    cur=head;
    struct Node* newhead=NULL,*newtail=NULL;
    while(cur)
    {
        struct Node*copy=cur->next;
        struct Node*next=copy->next;
        if(newtail==NULL)
        {
            newhead=newtail=copy;
        }
        else
        {
            newtail->next=copy;
            newtail=copy;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;
}

  链表的常见OJ题我们先例举到这里，后续我们会持续更新的哦ovo~

  感谢观看，希望本篇文章会对您有所帮助。