链表分割

[编程题]链表分割

热度指数：107182 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

算法知识视频讲解

推荐

念润

思路

设置两个链表头，遍历原链表，一个追加小数链表，一个追加大数链表，最后将小数链表粘到大数链表前边即为结果。

代码

class Partition {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == nullptr){
            return nullptr;
        }//if
        ListNode *smallList = new ListNode(-1);
        ListNode *bigList = new ListNode(-1);
        ListNode *ps = smallList,*pb = bigList,*cur = head;
        while(cur){
            if(cur->val < x){
                ps->next = cur;
                ps = cur;
            }//if
            else{
                pb->next = cur;
                pb = cur;
            }//else
            cur = cur->next;
        }//while
        pb->next = nullptr;
        ps->next = bigList->next;
        return smallList->next;
    }
};

编辑于 2015-10-04 19:17:59 回复(15)

Python

KIng兮

我建立的链表是带头结点的链表，方法是结点的换位和链表重连
我知道还有另一种新建链表两个连接的方法 ，但是不太清楚两个方法那个会好一些
时间复杂度 还是 空间复杂度哪个会好一些？
语言 python3
def divsion(self,h,data):
    std = h
    h = h.next while h.data < data and h.next:
        std = std.next
        h = h.next
    std_x = h
    h = h.next while h: if h.data <= data:
            h = h.next
            std_x.next.next = std.next
            std.next = std_x.next
            std_x.next = h
            std = std.next else:
            std_x = std_x.next
            h = h.next

发表于 2020-02-11 21:48:51 回复(0)

Python

l一人在山旁l

设置两个链表一个放小于x的，一个放大于x的，最后组合到一起。python实现

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Partition:
    def partition(self, pHead, x):
        shead = ListNode(0)
        bhead = ListNode(0)
        newNode1 = shead
        newNode2 = bhead
        while pHead:
            if pHead.val<x:
                shead.next = pHead
                shead = shead.next
            else:
                bhead.next = pHead
                bhead = bhead.next
            pHead = pHead.next
        shead.next = newNode2.next
        bhead.next = None
        return newNode1.next

发表于 2019-02-19 18:31:43 回复(0)

Python

JemmyH

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Partition:
    def partition(self, pHead, x):
        # write code here
        if pHead == None:
            return None
        h = ListNode(None)
        h1 = ListNode(pHead.val)
        pHead = pHead.next
        h.next = h1
        if h1.val < x:
            front = h1
        else:
            front = h
        last = h1
        while pHead != None:
            tem = ListNode(pHead.val)
            if pHead.val >= x:
                last.next = tem
                last = tem
            elif pHead.val < x:
                tem.next = front.next
                front.next = tem
                front = tem
            pHead = pHead.next
        return h.next

发表于 2018-08-15 00:20:54 回复(0)

Python

亲爱的暴躁的热心网友皮皮文

怎么贴python的格式也不正确就share一下解题思路。

读完题目没明白是什么意思i，以为分割成两个部分，也没说是否为两个链表。我就把整个链表排序后提交了，不对，然后看答案明白了是两个链表。

Anyway最后搞懂了说下解题思路。

1.关键词两个链表（new两个新的链表），并且最后要做两个链表的缝合手术（small large遍历完.Next都为None所以这时缝合起来即可）

2.外层循环遍历pHead链表内层判断语句往里面装填

3.detials:注意最后返回的是指针

发表于 2018-06-16 16:16:54 回复(0)

Python

华科平凡

python solution

class Partition:
    def partition(self, pHead, x):

        part1,part2=[],[]
        while pHead:
            if pHead.val<x:
                part1.append(pHead.val)
            else:
                part2.append(pHead.val)
            pHead=pHead.next

        dummy=ListNode(0)
        pre=dummy
        for i in part1+part2:
            node=ListNode(i)
            pre.next=node
            pre=pre.next
        return dummy.next

发表于 2017-10-31 15:38:58 回复(0)

Python

Yannyezixin

思路：

迭代访问链表，用一个新链表链接小于x的结点，另一个新链表链接大于x的结点。最后链接两个链表，返回第一个新链表的头结点即可

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Partition:
    def partition(self, pHead, x):
        if not pHead:
            return None
        
        dummybefore = before = ListNode(0)
        dummyafter = after = ListNode(0)
        
        while pHead:
            if pHead.val < x:
                before.next = pHead
                before = before.next
            else:
                after.next = pHead
                after = after.next
            pHead = pHead.next
            
        after.next = None
        before.next = dummyafter.next
        return dummybefore.next

发表于 2016-08-02 08:52:08 回复(1)