您现在的位置是:首页 >其他 >单链表OJ题:LeetCode--面试题:02.04 分割链表网站首页其他

单链表OJ题:LeetCode--面试题:02.04 分割链表

stackY、 2024-06-17 10:19:00
简介单链表OJ题:LeetCode--面试题:02.04 分割链表

朋友们、伙计们,我们又见面了,今天给大家带来的是LeetCode面试题:02.04.分割链表

数 据 结 构:数据结构专栏
作          者:stackY、

LeetCode :LeetCode刷题训练营

 LeetCode面试题:02.04.分割链表https://leetcode.cn/problems/partition-list-lcci/

牛客网:CM11 分割链表https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking

目录

1.题目介绍

2.实例演示

3.解题思路

3.1不带哨兵位的头结点

3.2带哨兵位的头结点


1.题目介绍

LeetCode:

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

不需要 保留 每个分区中各节点的初始相对位置。

牛客网:

现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。

两个题目描述都差不多,但是牛客网要求不能改变相对位置,LeetCode则不在乎相对位置,那么我们就不改变相对位置了。

2.实例演示

3.解题思路

链表的分割有两种方法:

1.不带哨兵位的头结点

2.带哨兵位的头结点

(两种方法都比较简单,但是带哨兵位的话会稍微的方便一点,这里考虑到有的老铁不知道哨兵位,因此我们两种方法都来演示一下)

3.1不带哨兵位的头结点

不带哨兵位就是直接尾插法:创建两个新的链表,遍历原链表,将小于x的结点尾插到第一个链表head1中,将大于等于x的结点尾插到head2中,尾插结束后将tail2指向的next置为NULL,与原链表断开,然后将head2链接在head1的后面,这里要考虑特殊情况:

1.两个链表第一次尾插时需要注意空指针的问题。

2.在遍历完原链表之后,如果head1为空时可以直接返回head2,如果head2为空,可以直接返回head1。

3.好多老铁好奇为什么不把tail1的next也置为空,这里可以置为空也可以不置为空,因为在下面链接的时候会改变tail1的next。

 

LeetCode - 代码演示(C语言实现):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* partition(struct ListNode* head, int x){

    //创建两个新的链表
    struct ListNode* head1 = NULL;
    struct ListNode* tail1 = NULL;
    struct ListNode* head2 = NULL;
    struct ListNode* tail2 = NULL;
    struct ListNode* cur = head;
    //遍历
    while(cur)
    {
        //小于x的插入第一个链表
        if(cur->val < x)
        {
            //第一次尾插
            if(tail1 == NULL)
            {
                head1 = tail1 = cur;
            }
            else
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
        }
        //大于或等于x的插入第二个链表
        else
        {
            if(tail2 == NULL)
            {
                head2 = tail2 = cur;
            }
            else
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    if(tail2 != NULL)
    {
        tail2->next = NULL;
    }
    //判断特殊情况
    if(head1 == NULL)
    {
        return head2;
    }
    if(head2 == NULL)
    {
        return head1;
    }
    //链接第一个链表和第二个链表
    tail1->next = head2;
    return head1;
}

牛客网 - 代码实现(C++实现):

/*
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
        //创建两个新的链表
    ListNode* head1 = NULL;
    ListNode* tail1 = NULL;
    ListNode* head2 = NULL;
    ListNode* tail2 = NULL;
    ListNode* cur = pHead;
    //遍历
    while(cur)
    {
        //小于x的插入第一个链表
        if(cur->val < x)
        {
            //第一次尾插
            if(tail1 == NULL)
            {
                head1 = tail1 = cur;
            }
            else
            {
                tail1->next = cur;
                tail1 = tail1->next;
            }
        }
        //大于或等于x的插入第二个链表
        else
        {
            if(tail2 == NULL)
            {
                head2 = tail2 = cur;
            }
            else
            {
                tail2->next = cur;
                tail2 = tail2->next;
            }
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    if(tail2 != NULL)
    {
        tail2->next = NULL;
    }
    //判断特殊情况
    if(head1 == NULL)
    {
        return head2;
    }
    if(head2 == NULL)
    {
        return head1;
    }
    //链接第一个链表和第二个链表
    tail1->next = head2;
    return head1;
    }
};

3.2带哨兵位的头结点

带哨兵位的头结点相比较于不带哨兵位的头结点的方法就略显简便,不需要考虑太多的NULL指针的问题,我们依旧采用的是直接尾插法:创建两个新的链表,遍历原链表,将小于x的结点尾插到第一个链表head1中,将大于等于x的结点尾插到head2中,尾插结束后将head2指向的next置为NULL,与原链表断开,然后将head2链接在head1的后面,这里就不需要考虑空指针的问题,直接尾插,尾插结束之后,不能直接将head2链接在tail1的后面,需要将head2的next链接,注意:哨兵位的头节点是动态开辟的,所以要释放掉,因此还要将链接之后的链表再链接在原链表的头上面,释放掉两个有哨兵位的链表:

 LeetCode - 代码演示(C语言实现):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode* head1, *tail1, *head2, *tail2;
    //创建带哨兵位的头结点
    head1 = tail1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    head2 = tail2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    struct ListNode* cur = head;
    while(cur)
    {
        //小的链接在第一个链表
        if(cur->val < x)
        {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else
        {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        //迭代
        cur = cur->next;
    }
    //断开与原链表的联系
    tail2->next = NULL;
    //链接两个新的链表
    tail1->next = head2->next;
    //将新链表链接在原来的头结点上面
    head = head1->next;
    //释放
    free(head1);
    free(head2);
    
    return head;
}

牛客网 - 代码实现(C++实现):

/*
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
        ListNode* head1, *tail1, *head2, *tail2;
    //创建带哨兵位的头结点
    head1 = tail1 = (ListNode*)malloc(sizeof(ListNode));
    head2 = tail2 = (ListNode*)malloc(sizeof(ListNode));
    
    struct ListNode* cur = pHead;
    while(cur)
    {
        //小的链接在第一个链表
        if(cur->val < x)
        {
            tail1->next = cur;
            tail1 = tail1->next;
        }
        else
        {
            tail2->next = cur;
            tail2 = tail2->next;
        }
        //迭代
        cur = cur->next;
    }
        //断开与原链表的联系
        tail2->next = NULL;
        //链接两个新的链表
        tail1->next = head2->next;
        //将新链表链接在原来的头结点上面
        pHead = head1->next;
        //释放
        free(head1);
        free(head2);
        
        return pHead;
    }
};

今天的博客就分享到这里,喜欢的老铁留下你的三连,感谢感谢!我们下期再见!!

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。