链表OJ（2）

柔光的暖阳◎ 2023-10-13 09:41 13阅读 0赞

**目录**

一、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的

二、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

三、 链表的回文结构

四、 输入两个链表，找出它们的第一个公共结点

五、 给定一个链表，判断链表中是否有环

六、 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL

七、 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝

--------------------

不要躺平，去发光！

--------------------

### 一、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 ###

[https://leetcode.cn/problems/merge-two-sorted-lists/][https_leetcode.cn_problems_merge-two-sorted-lists]

**代码1展示**：（不带头）

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        if (list1 == NULL)
        {
            return list2;
        }
        if (list2 == NULL)
        {
            return list1;
        }
        struct ListNode* head = NULL;
        struct ListNode* tail = NULL;
        while (list1 && list2)
        {
            struct ListNode* next1 = list1->next;
            struct ListNode* next2 = list2->next;
            if ((list1->val) < (list2->val))
            {
                if (tail == NULL)
                {
                    head = list1;
                    tail = list1;
                }
                else
                {
                    tail->next = list1;
                    tail = list1;
                } 
                list1 = next1;
            }
            else
            {
                if (tail == NULL)
                {
                    head = list2;
                    tail = list2;
                }
                else
                {
                    tail->next = list2;
                    tail = list2;
                } 
                list2 = next2;
            }
        }
    
        if (list1 != NULL)
        {
            tail->next = list1;
           
        }
    
        if (list2 != NULL)
        {
            tail->next = list2;
        }
        return head;
    }

**思路**：每次取小的节点尾插到新的节点

> **注意**：其中一个为空的情况要注意

> 有头单链表：head->next指的是第一个节点的地址（带头，相当于开头多了一个节点，但是节点里面的val不确定，next指向下一个节点）； 无头单链表：head指的是第一个节点的地址； OJ题默认不带头

**代码2展示**：（带头）

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
        struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头
        struct ListNode* tail = head;
        head->next = NULL;//就是含有值的节点的第一个
        while (list1 && list2)
        {
            struct ListNode* next1 = list1->next;
            struct ListNode* next2 = list2->next;
            if ((list1->val) < (list2->val))
            {
                tail->next = list1;
                tail = list1;
                list1 = next1;
            }
            else
            {
                tail->next = list2;
                tail = list2;
                list2 = next2;
            }
        }
    
        if (list1 != NULL)
        {
            tail->next = list1;
           
        }
        if (list2 != NULL)
        {
            tail->next = list2;
        }
        struct ListNode* list = head->next;
        free(head);
        return list;
    }

**思路**：每次取小的节点尾插到新的节点

> **注意**：mallloc的一个地址，到最后要进行释放。

### 二、编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 ###

[https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking][https_www.nowcoder.com_practice_0e27e0b064de4eacac178676ef9c9d70_tpId_8_tqId_11004_rp_2_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]

**代码展示**：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };*/
    class Partition {
    public:
        ListNode* partition(ListNode* pHead, int x) {
            // write code here
            struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
            struct ListNode* LessTail = LessHead;
            struct ListNode* GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
            struct ListNode* GreaterTail = GreaterHead;
            struct ListNode* cur = pHead;
            while (cur != NULL)
            {
                if (cur->val < x)
                {
                    LessTail->next = cur;
                    LessTail = cur;
                }
                else
                {
                    GreaterTail->next = cur;
                    GreaterTail = cur;
                }
                cur = cur->next;
            }
            GreaterTail->next = NULL;
            LessTail->next = GreaterHead->next;
            struct ListNode* list = LessHead->next;
            free(LessHead);
            free(GreaterHead);
            return list;
    
    
        }
    };

**思路**：小于x的插入到一个链表，大于等于x的插入到一个链表，链表1和链表2合并（用带头的）

> **注意**：链表2的最后一项要指向NULL，如果不指向NULL，就可能造成死循环【链表的题，要注意头和尾】

### 三、 链表的回文结构 ###

[https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking][https_www.nowcoder.com_practice_d281619e4b3e4a60a2cc66ea32855bfa_tpId_49_tqId_29370_rp_1_ru_activity_oj_qru_ta_2016test_question-ranking]

**代码展示**：

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };*/
    
    struct ListNode* reverseList(struct ListNode* head){
        struct ListNode* cur = head;
        struct ListNode* prev = NULL;
        while(cur)
        {
            struct ListNode* next = cur->next;
            cur ->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
    
    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;
    }
    
    class PalindromeList {
    public:
        bool chkPalindrome(ListNode* A) {
            // write code here
            struct ListNode* mid = middleNode(A);
            struct ListNode* rHead = reverseList(mid);
            while (A && rHead)
            {
                if (A->val == rHead->val)
                {
                    A = A->next;
                    rHead = rHead->next;
                }
                else 
                {
                    return false;
                }
            }
            return true;
        }
    };

**思路**：首先找到链表的中间的地址（奇数个）或者是中间的第二个地址（偶数个）作为第二个链表的头，然后逆置第二个链表，然后第原始链表和第二个链表进行比较。（当原始链表和第二个链表有一个是空的时候，就可以跳出循环，说明是回文链表

### 四、 输入两个链表，找出它们的第一个公共结点 ###

[https://leetcode.cn/problems/intersection-of-two-linked-lists/description/][https_leetcode.cn_problems_intersection-of-two-linked-lists_description]

**代码展示**：（思路2）

/**
     * 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;
        struct ListNode* tailB = headB;
        int lenA = 1;
        int lenB = 1;
        while (tailA->next != NULL)
        {
            tailA = tailA->next;
            lenA++;
        }
        while (tailB->next != NULL)
        {
            tailB = tailB->next;
            lenB++;
        }
        if (tailA != tailB)
        {
            return NULL;
        }
        //找到节点
        int gap = abs(lenA - lenB);
        //想法值得学习，大小
        struct ListNode* shortList = headA;
        struct ListNode* longList = headB;
        if (lenA > lenB)
        {
            shortList = headB;
            longList = headA;
        }
        while(gap--)
        {
            longList = longList->next;
        }
        while (longList && shortList)
        {
            if (longList == shortList)
            {
                return longList;
            }
            longList = longList->next;
            shortList = shortList->next;
        }
        return NULL;
    }

**思路1**：A链表每一个节点和B链表依次比较，如果有相等，就是相交，第一个相等的就是交点。

（判断是否是相交，交点是多少）时间复杂度：O(M\*N)

**思路2**：当尾节点的地址相同的时候，就是相交。（判断是否是相交）

求出两个链表的长度，然后链表长的先走两个链表的差值，然后两个链表一起走，当地址相同的时候，位置就是节点（交点是多少）时间复杂度：O(M+N)

> **注意**：（1）地址相同，不是值相等（值相等不一定是节点）
> 
> （2）编译器执行的是语法错误，编译器不能检查出执行逻辑，所以在最后要加上return NULL（因为上面有一个if之后返回一个值，编译器会认为不满足这个if条件的时候没有返回值）;

### 五、 给定一个链表，判断链表中是否有环 ###

[https://leetcode.cn/problems/linked-list-cycle/submissions/][https_leetcode.cn_problems_linked-list-cycle_submissions]

**代码展示**：

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    bool hasCycle(struct ListNode *head) 
    {
        struct ListNode* slow = head;
        struct ListNode* fast = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                return true;
            }
        }
        return false;
    }

**思路**：\[快慢指针\]slow一次走一步，fast一次走两步，当slow进环之后，开启追赶模式，最后fast追上slow；不带环fast->next或者fast就会是NULL，带环的话就不会是NULL；

> **注意**：刚开始fast等于slow，所以再循环里面先赋值，后比较

> （1）slow一次走一步,fast一次走两步，一定能追上。
> 
> 当slow走一半的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少1，所以就一定能追上。【距离为0，追上】
> 
> （2）slow一次走一步,fast一次走三步，不一定能追上。
> 
> 当slow走1/3的时候，fast开始进环。此时两者的距离为N，每次之后，距离会减少2，如果距离为奇数，就会错过，【偶数可以追上】，此时距离又为环数-1【偶数追上，奇数就永远追不上】，所以不一定能追上。

### 六、 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 NULL ###

[https://leetcode.cn/problems/linked-list-cycle-ii/description/][https_leetcode.cn_problems_linked-list-cycle-ii_description]

**代码展示**：(思路一）

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    struct ListNode *detectCycle(struct ListNode *head) 
    {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow)
            {
                struct ListNode* meet = slow;
                while (head != meet)
                {
                    meet = meet->next;
                    head = head->next;
                }
                return meet;
            }
        }
        return NULL;
    }

**思路1**：假设，进入环之前的距离为L；slow两者相遇后之前，进入环之后走的距离x；进入环之后两者的距离为N ；环的长度为C \[快慢指针\]slow一次走一步，fast一次走两步，fast是slow的两倍【slow绝对不会走一圈被fast追上，而是没有走一圈就被fast给追上了，因为当slow进入环之后，两者的距离为N，N肯定小于环数，所以两者相遇的时候，slow肯定没有走完一圈，所以slow走得距离为进入环之前的距离L+两者相遇后之前，进入环之后走的距离x即L+x;fast走的距离为nC+L+x; n\*C+L+x=2(L+x),----n\*C=L+x;n为未知数】【slow进环之后，fast不可能走完一圈】n\*C=L+x:能证明，一个从进入链表走，一个从相遇的那个节点走，slow和fast在环入口处相遇。

**思路2**：转换成求链表交点。【从相遇处开始断开】meet作为尾，meet->next作为头 ，head给出，求交点。

### 七、 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝 ###

[https://leetcode.cn/problems/copy-list-with-random-pointer/description/][https_leetcode.cn_problems_copy-list-with-random-pointer_description]

**代码展示**：

/**
     * Definition for a Node.
     * struct Node {
     *     int val;
     *     struct Node *next;
     *     struct Node *random;
     * };
     */
    
    struct Node* copyRandomList(struct Node* head)
    {
    	struct Node* cur = head;
        //拷贝节点链接
        while (cur!= NULL)
        {
            struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
            copy->val = cur->val;
            copy->next = cur->next;
            cur->next = copy;
            cur = cur->next->next;
        }
        //random
        cur = head;
        while (cur != NULL)
        {
            if (cur->random == NULL)
            {
                cur->next->random = NULL;
            }
            else
            {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        //摘下来、链接
        struct Node* copyHead = NULL;
        struct Node* copyTail = NULL;
        cur = head;
        while (cur != NULL)
        {
            struct Node* copy = cur->next;
            struct Node* next = copy->next;
            if (copyHead == NULL)
            {
                copyHead  = copyTail = copy;
            }
            else
            {
                copyTail->next = copy;
                copyTail = copy;
            }
            cur = next;
        }
        return copyHead;
    
    }

**思路**：拷贝每一个节点连接在原节点之后，链接拷贝节点的random，新的random在前面的random的next。最后，把拷贝节点解下来，链接起来。【索引从0开始】

--------------------

链表其他题

力扣：[https://leetcode.cn/tag/linked-list/problemset/][https_leetcode.cn_tag_linked-list_problemset]

牛客网：[https://www.nowcoder.com/exam/oj][https_www.nowcoder.com_exam_oj]

[https_leetcode.cn_problems_merge-two-sorted-lists]: https://leetcode.cn/problems/merge-two-sorted-lists/
[https_www.nowcoder.com_practice_0e27e0b064de4eacac178676ef9c9d70_tpId_8_tqId_11004_rp_2_ru_activity_oj_qru_ta_cracking-the-coding-interview_question-ranking]: https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
[https_www.nowcoder.com_practice_d281619e4b3e4a60a2cc66ea32855bfa_tpId_49_tqId_29370_rp_1_ru_activity_oj_qru_ta_2016test_question-ranking]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[https_leetcode.cn_problems_intersection-of-two-linked-lists_description]: https://leetcode.cn/problems/intersection-of-two-linked-lists/description/
[https_leetcode.cn_problems_linked-list-cycle_submissions]: https://leetcode.cn/problems/linked-list-cycle/submissions/
[https_leetcode.cn_problems_linked-list-cycle-ii_description]: https://leetcode.cn/problems/linked-list-cycle-ii/description/
[https_leetcode.cn_problems_copy-list-with-random-pointer_description]: https://leetcode.cn/problems/copy-list-with-random-pointer/description/
[https_leetcode.cn_tag_linked-list_problemset]: https://leetcode.cn/tag/linked-list/problemset/
[https_www.nowcoder.com_exam_oj]: https://www.nowcoder.com/exam/oj