86. Partition List

# 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 """ if (head == None or head.next == None): return head else: i = head j = head.next j_prev = head # used in swapping nodes while(j != None): if (j.val < x): # swap A[i+1], A[j] # use four helper variable (plus the j_prev) to keep track of our lists... i_plus_one = i.next i_plus_two = i.next.next # will this be None? No. We know j is at least i.next, and j != None j_plus_one = j.next i.next = j j.next = i_plus_two j_prev.next = i_plus_one i_plus_one.next = j_plus_one # now shift i and j both forward ! i = i.next j = j_prev.next else: j = j.next return head