Python算法进阶 - 5（分割链表）

进阶 - 5（分割链表）"/>

Python算法进阶 - 5（分割链表）

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

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

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

来源：力扣（LeetCode）
链接：
 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def partition(self, head, x):before = before_head = ListNode(0)after = after_head = ListNode(0)while head:if head.val < x:before.next = headbefore = before.nextelse:after.next = headafter = after.nexthead = head.nextafter.next = Nonebefore.next = after_head.nextreturn before_head.next

这道题，自己虽然想到了大概，但是方法太low超时了，看下官方大神写的，借鉴思路，首先是创建一个哑节点（也及时L.nil）。

灵活运用，以前只局限于双链表才会有哑节点。

好处在于：为了算法实现更容易，我们使用了哑节点初始化。不能让哑节点成为返回链表中的一部分，因此在组合两个链表时需要向前移动一个节点。

思路：

用两个指针创建两个链表，小于x占一个链表，其他的是另一个链表。当第二个链表没有节点的时候，就可以将原来的两个链表进行连接起来就可以了。  

see you  细品！！！