链表高频笔试的OJ题

- 日理万妓 2023-09-26 17:04 85阅读 0赞

> **文章目录**
> 
> 一、合并两个有序链表
> 
> 解题代码
> 
> 二、反转链表
> 
> 解题代码
> 
> 三、分割链表
> 
> 解题代码 
> 
> 四、链表的回文结构
> 
> 解题代码
> 
> 五、链表相交
> 
> 解题代码
> 
> 六、环形链表
> 
> 解题代码
> 
> 七、复制带有随机指针的复制链表
> 
> 解题代码

## 一、合并两个有序链表 ##

> 题目来源：牛客网。
> 
> 题目难度：简单。
> 
> 题目描述：输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
> 
> 数据范围： 0 <= n <= 1000,-1000≤节点值≤1000，要求：空间复杂度 O(1)，时间复杂度 O(n）。

![11a28fc94a2644bf9d0a56b27c7e6e74.png][]

> **题解关键思路：**
> 
> 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->val<pHead2->val)
            {
                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) 。

![6bf97f30c62d4abead17e386cf86cbe2.png][]

> **题解关键思路：**
> 
> 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` 的节点之前。

![e946877e6e17448aa5dff08060548d89.png][]

> **题解关键思路：**
> 
> 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<x)
            {
                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` **，**请判断其是否为回文链表。如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

![a52711a6b5c443809ba2cfb988039059.png][]

> **题解关键思路：**
> 
> 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` 。

### ![b0ecf406576b46f3ac21b2df8ee7209d.png][] ###

> **题解关键思路：**
> 
> 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<countB)
        {
            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` 不作为参数进行传递**，仅仅是为了标识链表的实际情况。**不允许修改** 链表。

![e7d3c0759cd8445eb9d1db748d94d20b.png][]

> **题解关键思路：**
> 
> 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` ，该指针可以指向链表中的任何节点或空节点。构造这个链表的 **[深拷贝][Link 1]**。 深拷贝应该正好由n个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 `next` 指针和`random` 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。**复制链表中的指针都不应指向原链表中的节点** 。
> 
> 例如，如果原链表中有 `X` 和 `Y` 两个节点，其中 `X.random --> Y` 。那么在复制链表中对应的两个节点 `x` 和 `y` ，同样有 `x.random --> y` 。返回复制链表的头节点

![d237814566294dc7bc72c764b9db8251.png][]

> **题解关键思路：**
> 
> 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~
> 
> 感谢观看，希望本篇文章会对您有所帮助。

[11a28fc94a2644bf9d0a56b27c7e6e74.png]: https://img-blog.csdnimg.cn/11a28fc94a2644bf9d0a56b27c7e6e74.png
[6bf97f30c62d4abead17e386cf86cbe2.png]: https://img-blog.csdnimg.cn/6bf97f30c62d4abead17e386cf86cbe2.png
[e946877e6e17448aa5dff08060548d89.png]: https://img-blog.csdnimg.cn/e946877e6e17448aa5dff08060548d89.png
[a52711a6b5c443809ba2cfb988039059.png]: https://img-blog.csdnimg.cn/a52711a6b5c443809ba2cfb988039059.png
[b0ecf406576b46f3ac21b2df8ee7209d.png]: https://img-blog.csdnimg.cn/b0ecf406576b46f3ac21b2df8ee7209d.png
[e7d3c0759cd8445eb9d1db748d94d20b.png]: https://img-blog.csdnimg.cn/e7d3c0759cd8445eb9d1db748d94d20b.png
[Link 1]: https://baike.baidu.com/item/%E6%B7%B1%E6%8B%B7%E8%B4%9D/22785317?fr=aladdin
[d237814566294dc7bc72c764b9db8251.png]: https://img-blog.csdnimg.cn/d237814566294dc7bc72c764b9db8251.png