Split list

Write a program to split the linked list based on x so that all nodes less than x rank before those greater than or equal to x. If the list contains x, x only needs to appear after the element less than x (as shown below). The partition element X only needs to be in the “right half”; it does not need to be placed between the left and right parts.

Example:

Input: the head = 3 – > 5-8 – > > 5-10 – > > 2 – > 1, x = 5 output: 3 – > 1 – > 2 – > 10 – > 5 – > – > 8

Java way: topic, only need to take less than the number of x to the front, other do not require, so create a p, q) to help us achieve, q used to traverse the list, found that less than the number of x and p exchange, because p is in the front at the beginning, so in a disguised form of equal to bring value to the forefront, every exchange is p = p.n ext

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode p = head;
        ListNode q = head;

        while(q! =null){if(q.val<x){
                int tmp = p.val;
                p.val = q.val;
                q.val = tmp;
                p = p.next;
            }
            q = q.next;
        }
        returnhead; }}Copy the code

Iterate three times to get values greater than x, equal to x, and less than x, then iterate and assign them to the 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
        """
        res = []
        p = head
        p_max = head
        p_D = head
        p_min = head
        while p_max :
            if p_max.val>x:
                res.append(p_max.val)
            p_max = p_max.next

        while p_D :
            if p_D.val==x:
                res.append(p_D.val)
            p_D = p_D.next

        while p_min :
            if p_min.val<x:
                res.append(p_min.val)
            p_min = p_min.next

 
        while p:
            p.val =res.pop()
            p = p.next
        return head
Copy the code