【Leetcode】单链表oj(下)，难度提升，快来做做.

🧸🧸🧸各位巨佬大家好，我是猪皮兄弟🧸🧸🧸

文章目录

废话不多说，直接来做题！！

一、📖链表分割

newcoder链表分割

思路:malloc一个新的头，将比x小的结点依次链接在后面，并且，定义一个prev可以将原链表的移走结点的其他结点连起来，最后，将两个链表链接起来返回就可以了

class Partition {
public:
    ListNode*partition(ListNode* pHead,int x){// write code here
        ListNode* newhead=(ListNode*)malloc(sizeof(ListNode));
        ListNode*tail=newhead;
        ListNode*prev;
        newhead->next=nullptr;
        ListNode*cur=pHead;while(cur){if(cur->val<x){if(cur==pHead){
                    tail->next=pHead;
                    pHead=pHead->next;
                    cur=pHead;
                    tail=tail->next;}else{
                    tail->next=cur;
                    prev->next=cur->next;
                    cur=cur->next;
                    tail=tail->next;}}else{
                prev=cur;
                cur=cur->next;}}
        tail->next=pHead;
        ListNode*ret=newhead->next;free(newhead);return ret;}};

二、📖回文链表

Leedcode回文链表
因为要求时间复杂度O(N)，空间复杂度O(1)

两种思路
1、因为知道链表的长度不超过900，所以可以定义一个900长度的数组，遍历一次把值记录一下，然后按照数组的判断回文去判断
2、将后半段逆置，然后一个从头开始走，一个从尾开始走，相同则是回文

方法一：

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A){// write code hereint arr[900]={0};int count=0;
        ListNode*cur=A;int start=0;while(cur){
            arr[start++]=cur->val;
            count++;
            cur=cur->next;}int i;for(i=0;i<(count)/2;i++){if(arr[i]!=arr[count-i-1])return false;}return true;}};

方法二：

structListNode*middleNode(structListNode*head){structListNode*slow,*fast;
    slow=fast=head;while(fast&&fast->next){
        slow=slow->next;
        fast=fast->next->next;}return slow;}structListNode*reverseList(structListNode*head){if(head==NULL){returnNULL;}structListNode*n1,*n2,*n3;
    n1=NULL;
    n2=head;
    n3=n2->next;while(n2){
        n2->next=n1;
        n1=n2;
        n2=n3;if(n3){
            n3=n3->next;}}return n1;}

bool isPalindrome(structListNode* head){structListNode*mid=middleNode(head);structListNode*rhead=reverseList(mid);while(head && rhead){if(head->val!=rhead->val){return false;}else{
            head=head->next;
            rhead=rhead->next;}}return true;}

三、📖相交链表

Leetcode相交链表
思路:先遍历两个链表，记录长度，然后通过快慢指针，快指针先走差距步，然后一起走，就可以找到fast==slow的结点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){int count1=0,count2=0;
        ListNode* cur1,*cur2;
        cur1=headA;
        cur2=headB;while(cur1){
            count1++;
            cur1=cur1->next;}while(cur2){
            count2++;
            cur2=cur2->next;}
        ListNode*fast,*slow;if(count1>count2){
            fast=headA;
            slow=headB;}else{
            fast=headB;
            slow=headA;}for(int i=0;i<abs(count1-count2);i++){
            fast=fast->next;}while(fast&&slow){if(fast==slow)return fast;
            fast=fast->next;
            slow=slow->next;}return nullptr;}};

四、📖环形链表(中等)

Leetcode环形链表

**两种思路：
1、一个指针从相遇点开始走，一个结点从起点开始走，最终会在相交处相遇
解释：
当slow进环以后，fast在slow的位置或者在环的任意位置，但是fast的速度是slow的二倍，所以必定会在一圈之内追上slow，然后可推导出如下公式

2、在相遇点断开环，然后按照上面的相交链表来写**

思路一：

class Solution {
public:
    ListNode *detectCycle(ListNode *head){
        ListNode*slow,*fast;
        slow=fast=head;
        ListNode*meet;while(fast&&fast->next){
            fast=fast->next->next;
            slow=slow->next;if(fast==slow){
                meet=fast;while(meet!=head){
                    meet=meet->next;
                    head=head->next;}return meet;}}return nullptr;}};

思路二：
这个就不写了，就是找到相遇点断开用相交链表的方法

五、📖复制带随机指针的链表（中等）

Leetcode复制带随机指针的链表

思路:首先遍历一次链表，复制前一个结点并插入（因为这时还没有整个链表复制完，所以，random是不完整的，还不能够在这里进行处理），然后再遍历一次链表，将random进行处理，最后还需要遍历一次链表，将copy的结点取下来

class Solution {
public:
    Node*CreateNode(int val){
        Node*node=(Node*)malloc(sizeof(Node));
        node->val=val;
        node->next=nullptr;
        node->random=nullptr;return node;}
    Node*copyRandomList(Node* head){if(!head)return nullptr;
        Node*cur=head;
        Node*next=cur->next;
        Node*copy;while(cur){
            copy=CreateNode(cur->val);
            copy->next=cur->next;
            cur->next=copy;
            cur=copy->next;}
        cur=head;
        copy=cur->next;while(cur){if(cur->random==nullptr)
            copy->random=nullptr;else
            copy->random=cur->random->next;
            cur=copy->next;if(cur)
            copy=cur->next;}
        Node*newhead=(Node*)malloc(sizeof(Node));
        newhead->next=nullptr;
        Node*tail=newhead;

        cur=head;
        copy=head->next;while(cur){
            cur->next=copy->next;
            tail->next=copy;
            tail=copy;
            cur=cur->next;if(cur)
            copy=cur->next;}

        tail->next=nullptr;
        Node* ret=newhead->next;free(newhead);return ret;}};

六、📖链表oj总结

链表oj就暂时更新到这里了，难度还是不小的，需要慢慢琢磨，在后期还会有很多的oj训练与大家分享，谢谢大家的支持！！