LeetCode | 面试题 02.04. 分割链表

简介: LeetCode | 面试题 02.04. 分割链表

LeetCode | 面试题 02.04. 分割链表

OJ链接

简单的做法:

  • 创建两个带头空链表,大链表和小链表,最后小链表的尾结点和大链表的头结点连接起来

代码如下:

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){
    if(head == NULL)
        return head;
    //创建带头的大小链表
    ListNode* lessHead,*lessTail;
    ListNode* greaterHead,*greaterTail;
    //创建大小链表的哨兵位
    lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));
    greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
    //遍历链表,将节点放到大小链表中
    ListNode* cur = head;
    while(cur)
    {
        if(cur->val < x)
        {
            //放到小链表中
            lessTail->next = cur;
            lessTail = lessTail->next;
        }
        else
        {
            //放到大链表中
            greaterTail->next = cur;
            greaterTail = greaterTail->next;
        }
        cur = cur->next;
    }
    if(greaterTail)
        greaterTail->next = NULL;
    //小链表的尾和大链表的头连接起来
    lessTail->next = greaterHead->next;
    //把动态开辟的空间连接起来
    free(greaterHead);
    ListNode* retHead = lessHead->next;
    free(lessHead);
    return retHead;
}
相关文章
|
1月前
|
算法
【数组相关面试题】LeetCode试题
【数组相关面试题】LeetCode试题
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
4天前
【力扣】21. 合并两个有序链表
【力扣】21. 合并两个有序链表
|
1月前
|
存储 JavaScript
leetcode82. 删除排序链表中的重复元素 II
leetcode82. 删除排序链表中的重复元素 II
22 0
|
1月前
leetcode83. 删除排序链表中的重复元素
leetcode83. 删除排序链表中的重复元素
10 0
|
1月前
leetcode2807.在链表中插入最大公约数
leetcode2807.在链表中插入最大公约数
16 0
|
1月前
leetcode2487.从链表中移除节点
leetcode2487.从链表中移除节点
20 1
|
22天前
|
机器学习/深度学习 算法
力扣刷题日常(一)
力扣刷题日常(一)
20 2
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记
|
1月前
|
搜索推荐
《LeetCode》——LeetCode刷题日记3
《LeetCode》——LeetCode刷题日记3