数据结构：单链表的应用（力扣算法题）第三章

代码汇总：登录 - Gitee.com

前两章回顾：

​​​​​​数据结构：单链表的应用（力扣算法题）第一章-CSDN博客

数据结构：单链表的应用（力扣算法题）第二章-CSDN博客

1.链表分割

链表分割_牛客题霸_牛客网

理解题意：

思路：

创建两个链表（小链表，大链表），遍历原链表，小的尾插到小链表中，大的尾插到大链表中，再将小链表和大链表相连。

代码如下：

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        //定义两链表
        ListNode* lessHead, *lessTail;
        lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
        ListNode* greaterHead, *greaterTail;
        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
        //遍历
        ListNode* curr = pHead;
        while(curr)
        {
            //尾插到小链表
            if(curr->val < x)
            {
                lessTail->next = curr;
                lessTail = lessTail->next;
            }
            else{
                //尾插到大链表
                greaterTail->next = curr;
                greaterTail = greaterTail->next;
            }
            curr = curr->next;
        }
        //大链表尾结点置空
    greaterTail->next = NULL;
    //相连
    lessTail->next = greaterHead->next;
    ListNode* ret = lessHead->next;
    free(lessHead);
    free(greaterHead);
    return ret;
    }
};

最终通过测试。

2.随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

理解题意：

浅拷贝：对值的拷贝，如形参和实参。

深拷贝：重新生成一个新的地址，并保存相同的值。

满足题意的最终结果：

其中copyphead为复制后的链表，最终返回copyphead。

思路：

第一步：

定义一个指针curr，以此遍历phead链表，并且在遍历过程中，只要当前结点不为空，依次保存当前的结点到新链表copyHead。

新的结点均通过尾插连接。

但是对于杂乱无章的random指针，我们应该怎么做？

对于random指针，我们可以将所有指针都置为空，再依次遍历，首先，创建copycurr指针，将random指针依次遍历，但是对于随机的，向后或向前指向的指针，不太好改变，所以此种方法暂时放弃。

第二步：

（1）在原链表基础上拷贝结点

通过curr遍历，每遍历一个结点，都新申请一个结点的空间newnode并且新建立一个结点，将其尾插到原本的结点之后，使其完成 newnode -> next = curr -> next; curr -> next = newnode;再使curr指针指向原本链表的下一个结点……以此类推。

(2）放置random指针

此时，是将复制好的链表都插入到了原链表之间，通过copy -> random = curr -> random ->next;将其curr与copy相关联。

（3）断开新旧链表

使新链表的next指针指向它自己的结点，同时可以选择，（可选）使旧链表也指向自己的下一结点。

代码如下：

此时，这里有错：

发现我们缺少对空链表的解决。

typedef struct Node Node;
//申请结点
Node* buyNode(int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
//增加结点
void AddNode(Node* head)
{
    Node* curr = head;
    while(curr)
    {
        //创建一样的结点
        Node* newnode = buyNode(curr->val);
        Node* next = curr->next;//此处next用于保存原链表下一结点
        //插入  
        newnode->next = next;
        curr->next = newnode;
        curr = next;
    }
}
//放置random
void setRandom(Node* head)
{
    Node* curr = head;
    while(curr)
    {
        Node* copy = curr->next;
        if(curr->random)
        copy -> random = curr -> random ->next;
        curr = copy->next;
    }
}

struct Node* copyRandomList(struct Node* head) {
    if(head == NULL)
    {
        return head;
    }
	//(1)
    AddNode(head);
    //(2)
    setRandom(head);
    //(3)
    Node* curr = head;
    Node* copyHead,*copyTail;
    copyHead = copyTail = curr->next;
    while(copyTail->next)
    {
        curr = copyTail->next;
        copyTail->next = curr->next;
        copyTail = copyTail->next;
    }
    return copyHead;
}

最终通过测试。

本章完。