网站产品内页设计,母婴网站建设策划书,企业网站备案信息查询,广告设计模板免费目录 1. 题目描述及链接
2. 解题思路
2.1 思路1
2.2 思路2
2.3 思路3#xff08;本题采取该解法#xff09;
3. 题解程序 1. 题目描述及链接
题目链接#xff1a;面试题 02.04. 分割链表 - 力扣#xff08;LeetCode#xff09;
题目描述#xff1a;
给你一个链表…目录 1. 题目描述及链接
2. 解题思路
2.1 思路1
2.2 思路2
2.3 思路3本题采取该解法
3. 题解程序 1. 题目描述及链接
题目链接面试题 02.04. 分割链表 - 力扣LeetCode
题目描述
给你一个链表的头节点 head 和一个特定值 x 请你对链表进行分隔使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。 你不需要 保留 每个分区中各节点的初始相对位置。
2. 解题思路
2.1 思路1
创建结构体指针变量curNode遍历原链表
当curNode的val值大于给定的X时将该结点尾插后释放该结点
当curNode的val值小于给定的X时保持该结点不动再检查下一结点 2.2 思路2
重新创建一个新链表并为其设置一个哨兵位。
创建指针变量curNode遍历原链表当curNode的val值大于给定的X时进行尾插操作
当curNode的val值小于给定的X时进行头插操作。 2.3 思路3本题采取该解法
总思路
创建两个新链表大链表和小链表。
创建指针变量curNode遍历原链表当curNode的val值小于给定的X时尾插到小链表
当curNode的val值大于给定的X时尾插到大链表
具体思路
1为实现大小链表的正确尾插需要创建对应指针变量指向当前的尾结点并在插入后更新尾结点。分别命名为greaterTail和lessTail
2同时新建链表为空时空指针-next会导致空指针解引用。故而新链表为空需单独讨论较为麻烦。此处采用设置哨兵位分别记为greaterHead和greaterTail 3由于创建了头结点哨兵位最后需手动释放
4注意由于哨兵位并不存放实际有效的值故大链表链接到小链表尾部时实际链接的大链表第一个结点是greaterHead-next最后返回新链表的第一个结点是lessHead-next
5考虑特殊情况若原链表为空则大小链表仅有哨兵位即greaterHead-next为NULLlessTail-next也为NULL直接返回NULL即可。
3. 题解程序
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {if(headNULL){return NULL;}// 创建两个带头链表ListNode* lessHead,*lessTail;ListNode* greaterHead,*greaterTail;lessHeadlessTail(ListNode*)malloc(sizeof(ListNode));greaterHeadgreaterTail(ListNode*)malloc(sizeof(ListNode));// 遍历原链表将结点分别尾插到大小链表ListNode* curNodehead;while(curNode!NULL){if(curNode-val x){// 尾插到小链表中lessTail-nextcurNode;lessTaillessTail-next;}else{// 尾插到大链表中greaterTail-nextcurNode;greaterTailgreaterTail-next;}curNodecurNode-next;}greaterTail-nextNULL;// 链接大小链表小前大后lessTail-nextgreaterHead-next;// 存小链表第一个有效结点并释放头结点ListNode* newHeadlessHead-next;free(lessHead);free(greaterHead);lessHeadlessTailNULL;return newHead;
}
注意
1、必须要将大链表的尾指针的next指针置为NULL否则会成环报错为超出时间限制 分析如下 2、greaterTail-nextNULL 语句必须在 lessTail-nextgreaterHead-next语句之前
假设跳出while循环后的代码顺序如下
// 链接大小链表小前大后
lessTail-nextgreaterHead-next;
greaterTail-nextNULL;
提交报错如下 这个错误表明程序试图访问一个未正确对齐的内存地址
通常是由于结构体成员未正确初始化或内存分配问题导致的。
考虑原链表为[1]单个结点)x2的情况
由于在while循环中仅执行了if分支并没有执行else分支
greaterHead仅调用malloc申请了空间并未为其val及next赋值。
此时直接使用greaterTail-next为lessTail-next赋值会导致赋值为随机值。
令greaterTail-nextNULL 语句在 lessTail-nextgreaterHead-next语句之前可以保证greaterHead和greaterTail被初始化为NULL。
