【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;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

二、📖回文链表

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

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

方法一：

class PalindromeList {
public:
    bool chkPalindrome(ListNode* A) {
        // write code here
        int 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;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

方法二：

struct ListNode*middleNode(struct ListNode*head)
{
    struct ListNode*slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
    }
    return slow;
}

struct ListNode*reverseList(struct ListNode*head)
{
    if(head==NULL)
    {
        return NULL;
    }
    struct ListNode*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(struct ListNode* head){

    struct ListNode*mid=middleNode(head);
    struct ListNode*rhead=reverseList(mid);
    while(head && rhead) 
    {
        if(head->val!=rhead->val)
        {
            return false;
        }
        else
        {
            head=head->next;
            rhead=rhead->next;
        }
        

    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

三、📖相交链表

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;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

四、📖环形链表(中等)

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;



    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

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

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;


    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

六、📖链表oj总结

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