0086.md

86. Partition List

Java Solution(s)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-101), dummy2 = new ListNode(-101);
        ListNode left = dummy1, right = dummy2;

        while (head != null) {
            if (head.val < x) {
                left.next = head;
                left = left.next;
            } else {
                right.next = head;
                right = right.next;
            }
            head = head.next;
        }
        right.next = null;
        left.next = dummy2.next;
        return dummy1.next;
    }
}

Python Solutions

# 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]:
        dummy1: ListNode = ListNode(-101)
        dummy2: ListNode = ListNode(-101)
        left: ListNode = dummy1
        right: ListNode = dummy2

        while head:
            if (head.val < x):
                left.next = head
                left = left.next
            else:
                right.next = head
                right = right.next

            head = head.next
        right.next = None
        left.next = dummy2.next
        return dummy1.next