leetcode86.分隔链表

86. 分隔链表

中等（链表）

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

img

输入： head = [1,4,3,2,5,2], x = 3
输出： [1,2,2,4,3,5]

示例 2：

输入： head = [2,1], x = 2
输出： [1,2]

代码一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        if not head:
            return head
        root = ListNode(0) # 哨兵节点，防止一开始的节点大于x
        root.next = head
        pre = root
        cur = head
        flag = False
        temp = temp1 = ListNode(0) # 将需要调换到前面的所有小于x的节点存到一个新链表中
        while cur:
            if cur.val >= x and not flag:  # 记录此处的节点，需要在这里插入新链表
                pre1 = pre 
                cur1 = cur
                flag = True
            if cur.val < x and flag:
                temp.next = ListNode(cur.val)  # 往新链表添加节点
                temp = temp.next
                pre.next = cur.next  # 原链表要删除当前节点
                cur = cur.next
                continue
            pre = pre.next
            cur = cur.next
        if temp1.next: # 判断新链表是否有节点，有的话插入到前面记录的位置
            pre1.next = temp1.next
            temp.next = cur1
        return root.next

思路：

大体思路是：将第一个大于等于x值的节点后面的所有小于x值的节点存到一个新链表中，原链表中的这些节点都删除，将新链表插入到第一个大于等于x值的节点之前。

代码二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        if not head:
            return head
        s = ListNode(0)
        s1 = s
        l = ListNode(0)
        l1 = l
        while head:
            if head.val < x:
                s1.next = ListNode(head.val)
                s1 = s1.next
                head = head.next
                continue
            l1.next = ListNode(head.val)
            l1 = l1.next
            head = head.next
        s1.next = l.next
        return s.next

思路：

大小节点存放到不同的两个链表，思路更简单一些，但是效率低了一些，空间复杂度更高。