题目:86. 分隔链表
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
解题:
1、使用两个链表分别存储<x的数和>=x的数,最后将两个链表进行拼接。
代码:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
head1 = ListNode(0)
head2 = ListNode(0)
p = head1
q = head2
cur = head
while cur:
if cur.val < x:
p.next = cur
p = p.next
else:
q.next = cur
q = q.next
cur = cur.next
p.next = head2.next
q.next = None
return head1.next