leetcode刷题04--链表划分--T86

题目:

image.png

---

自己的思路:
两个指针,一个指前:B 一个指后:A 还有一个尾节点:tail,tail_1(记录原来的尾位置,永不变,用来对比)
第一步: 遍历A,每次B保存A前面那个节点,A先找到第一个大于x的节点,将其放到最后面
//A指向的节点放到最后面
tail->next = A;
//把A和前一个节点断开
B->next = A->next;
//A指向节点之后的节点置空(设置为尾节点)
A->next = null;
//更新尾指针
tail = A;
//A恢复到B之后的位置
A = B->next;
第二步: 继续遍历A,遇到大于x的节点重复上面操作,当A遍历到了tail_1的位置,结束

...行不通!
还是参考一下ppt里给的思路吧!

image.png
image.png

其实还是挺容易理解的,用了两个临时链表,一个存大的,一个存小的
最后把小的尾部借上大的的第一个(有值的)节点
就可以了

代码如下:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        //设置两个临时头结点
        ListNode less_head(0);
        ListNode more_head(0);
        //设置分别指向这两个头结点的指针,注意这里要用'&'符号
        ListNode* less_ptr = &less_head;
        ListNode* more_ptr = &more_head;
        //遍历
        while(head){
            if(head->val >= x){
                //大于
                more_ptr->next = head;
                more_ptr = more_ptr->next;
                
            }else{
                //小于
                less_ptr->next = head;
                less_ptr = less_ptr->next;
            }
            //下一个
            head = head->next;
        }

        
        //链接,此处注意,不是指针类型的节点要用'.'而不是'->'
        less_ptr->next = more_head.next;
        
        //置空
        more_ptr->next = NULL;
        return less_head.next;
        
    }
};

总结:

自己去想还是有难度,
开始想到了一个方案,却在实现过程中发现不可行,花了时间较多.
以后还是要注意一点的,如果10分钟思路不够明朗,就可以看ppt的思路了!
另外在写这个的时候还让自对指针的理解更深了一些

指针只是指向一个节点,却不完全是那个节点,另外'.''->'也有区别,
具体看代码里面

继续加油,剩下的时间看专业课!