链表OJ（2）

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

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

三、链表的回文结构

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

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

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

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

不要躺平，去发光！

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

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

代码展示：

/*
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

代码展示：

/*
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/

代码展示：（思路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/

代码展示：

/**
 * 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/

代码展示：(思路一）

/**
 * 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/

代码展示：

/**
 * 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://www.nowcoder.com/exam/oj

原文链接：https://blog.csdn.net/m0_57388581/article/details/131501329

链表OJ（2）

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

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

三、 链表的回文结构

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

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

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

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

相关推荐

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

三、链表的回文结构

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

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

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

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