【数据结构】_链表经典算法OJ：分割链表（力扣—中等）

目录

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为NULL，lessTail->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(head==NULL){
        return NULL;
    }
    // 创建两个带头链表
    ListNode* lessHead,*lessTail;
    ListNode* greaterHead,*greaterTail;
    lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));
    greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));
    // 遍历原链表，将结点分别尾插到大小链表
    ListNode* curNode=head;
    while(curNode!=NULL){
        if(curNode->val < x){
            // 尾插到小链表中
            lessTail->next=curNode;
            lessTail=lessTail->next;
        }else{
            // 尾插到大链表中
            greaterTail->next=curNode;
            greaterTail=greaterTail->next;
        }
        curNode=curNode->next;
    }
    greaterTail->next=NULL;
    // 链接大小链表：小前大后
    lessTail->next=greaterHead->next;
    // 存小链表第一个有效结点，并释放头结点
    ListNode* newHead=lessHead->next;
    free(lessHead);
    free(greaterHead);
    lessHead=lessTail=NULL;
    return newHead;
}

注意：

1、必须要将大链表的尾指针的next指针置为NULL，否则会成环，报错为超出时间限制：

分析如下：

2、greaterTail->next=NULL 语句必须在 lessTail->next=greaterHead->next语句之前：

假设跳出while循环后的代码顺序如下：

// 链接大小链表：小前大后
lessTail->next=greaterHead->next;
greaterTail->next=NULL;

提交报错如下：

这个错误表明程序试图访问一个未正确对齐的内存地址，

通常是由于结构体成员未正确初始化或内存分配问题导致的。

考虑原链表为[1]（单个结点)，x=2的情况：

由于在while循环中仅执行了if分支并没有执行else分支，

greaterHead仅调用malloc申请了空间，并未为其val及next赋值。

此时直接使用greaterTail->next为lessTail->next赋值，会导致赋值为随机值。

令greaterTail->next=NULL 语句在 lessTail->next=greaterHead->next语句之前，可以保证greaterHead和greaterTail被初始化为NULL。