【C++】CM11 链表分隔

ઇଓ 欢迎来阅读子豪的博客（剑指offer刷题篇）

☾ ⋆有什么宝贵的意见或建议可以在留言区留言

ღღ欢迎 素质三连 点赞 关注 收藏

 ❣ฅ码云仓库：补集王子 (YZH_skr) - Gitee.com

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

目录

 难点

思路

运用带哨兵位的头结点（尾插的题尽量都用哨兵位）

定义两个链表

尾插

连接+释放

考虑极端场景

需要把最后一个置空

整体代码

---

 难点

相对顺序不变

思路 运用带哨兵位的头结点（尾插的题尽量都用哨兵位） 定义两个链表

尾插

 

连接+释放

 

 

考虑极端场景

原来链表最后一个比x大

就会把大的那个写到新链表的最后一个去 但是这个的next是指向前面的 就会出现一个环

  

需要把最后一个置空

整体代码

class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) 
    {
        ListNode *greatertail , *greaterhead, *lesshead, *lesstail;
        greaterhead = greatertail = (struct ListNode*)malloc(sizeof(struct ListNode));    //哨兵位
        lesshead = lesstail = (struct ListNode*)malloc(sizeof(struct ListNode));    //哨兵位
        greaterhead -> next = NULL;
        lesshead ->next = NULL;
        
        struct ListNode* cur = pHead;    // 工具指针
        while(cur)
        {
            if(cur -> val < x)
            {
                lesstail -> next = cur;
                lesstail = lesstail->next;
            }
            else
            {
                greatertail -> next = cur;
                greatertail = greatertail->next;
            }
                cur = cur->next;
        }
        lesstail->next = greaterhead->next;
        greatertail->next = NULL;   
        
        struct ListNode* head = lesshead->next;

        free(greaterhead);
        free(lesshead);
        
        return head;
    }
};

记得 三连哦~