划分链表

划分链表

http://www.nowcoder.com/questionTerminal/1dc1036be38f45f19000e48abe00b12f

题目理解起来有点费劲:使所有小于x的节点都位于大于或等于x的节点之前,意思是只需要小于等于x的节点位于链表前面即可,不要求小于在前,等于在中,大于在后。

采用双哑节点+双指针,先构建中间链表,然后将两个链表合并:

  • 哑节点指向两个中间链表的头部
  • 指针指向两个中间链表的尾部

代码如下:

//
// Created by jt on 2020/9/24.
//
class Solution {
public:
    /**
     *
     * @param head ListNode类
     * @param x int整型
     * @return ListNode类
     */
    ListNode* partition(ListNode* head, int x) {
        // write code here
        ListNode dummy1(0), dummy2(0);
        ListNode *p = &dummy1, *q = &dummy2;
        ListNode *r = head;
        while (r) {
            if (r->val < x) {
                p->next = r; p = r;
            } else {
                q->next = r; q = r;
            }
            r = r->next;
        }
        p->next = dummy2.next;
        q->next = nullptr;
        return dummy1.next;
    }
};
刷遍天下无敌手 文章被收录于专栏

秋招刷题历程

全部评论
对呀!题目都理解了好久。 “使所有小于x的节点都位于大于或等于x的节点之前”。 斟酌了一下这句话, 1、小于X的节点肯定都在某个节点之前,所以你可能只需要移动小的节点 2、考虑这样一种情况,万一在链表里面没有找到X呢?那这些小节点要位于谁之前?答案是位于第一个比X大的那一个之前
点赞
送花
回复
分享
发布于 2021-07-24 23:34

相关推荐

6 2 评论
分享
牛客网
牛客企业服务