86. Partition List

1. 原始题目

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

2. 题目理解

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

但注意两个分区中每个节点的初始相对位置保持不变。

坑：空链表，x小于链表中所有值或大于链表中所有值。

3. 解题

思路：定义两个指针。ori指针始终在原链表中操作（<x的部分），new指针指向(>x的部分)。所以无需创建新结点。遍历完成后将两个链表合并即可。

 1 # Definition for singly-linked list.
 2 # class ListNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.next = None
 6 
 7 class Solution:
 8     def partition(self, head: ListNode, x: int) -> ListNode:
 9         if not head:
10             return None
11         new = ListNode(0)      # 定义一个新头结点，用于存放所有>x的数
12         new.next = None
13         recode_new = new
14          
15         ori = ListNode(0)      # 原始结点，保存所有原链表中<x的数
16         ori.next = head
17         recore_ori = ori
18         while ori and ori.next:       
19             if ori.next.val<x:         # 如果<x就接着往下走
20                 ori = ori.next
21             else:
22                 new.next = ori.next         # 否则加入到new链表中
23                 new = new.next
24                 ori.next = ori.next.next
25                 new.next = None
26         ori.next = recode_new.next           # 合并两个链表
27         
28         return recore_ori.next

验证：

 1 # 新建链表1
 2 listnode1 = ListNode_handle(None)
 3 s1 = [666,4,3,2,58,5,78,2,634,42,36,244,35,41,33,32,23,266]
 4 for i in s1:
 5     listnode1.add(i)
 6 listnode1.print_node(listnode1.head)
 7 
 8 s = Solution()
 9 head = s.partition(listnode1.head,137)
10 listnode1.print_node(head)

666 4 3 2 58 5 78 2 634 42 36 244 35 41 33 32 23 266
4 3 2 58 5 78 2 42 36 35 41 33 32 23 666 634 244 266