Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/86.html

86	Partition List

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

@tag-linkedlist

Algorithm

All nodes less than the given value are taken out to form a new linked list. At this time, the values of the remaining nodes in the original linked list are greater than or equal to the given value, as long as the original linked list is directly connected to the new linked list.

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
New:

Original: 4 -> 3 -> 2 -> 5 -> 2
New:   1

Original: 4 -> 3 -> 5 -> 2
New:   1 -> 2

Original: 4 -> 3 -> 5
New:   1 -> 2 -> 2

Original:
New:   1 -> 2 -> 2 -> 4 -> 3 -> 5

Code

  • 
    public class Partition_List {
    
    	/**
    	 * Definition for singly-linked list.
    	 * public class ListNode {
    	 *     int val;
    	 *     ListNode next;
    	 *     ListNode(int x) { val = x; }
    	 * }
    	 */
    	public class Solution {
    	    public ListNode partition(ListNode head, int x) {
    	        if (head == null) {
    	            return head;
    	        }
    
    	        ListNode lessList = new ListNode(0);
    	        ListNode moreList = new ListNode(0);
    
    	        ListNode lessHeadCopy = lessList;
    	        ListNode moreHeadCopy = moreList;
    
    	        int xCount = 0;
    	        ListNode current = head;
    	        while (current != null) {
    	            int num = current.val;
    
    	            if (num < x) {
    	                lessList.next = new ListNode(num);
    	                lessList = lessList.next;
    	            } else {
    	                moreList.next = new ListNode(num);
    	                moreList = moreList.next;
    	            }
    
    	            current = current.next;
    	        }
    
    	        // append target x
    	        while (xCount > 0) {
    	            lessList.next = new ListNode(x);
    	            lessList = lessList.next;
    
    	            xCount--;
    	        }
    
    	        // connect two lists
    	        lessList.next = moreHeadCopy.next;
    
    	        return lessHeadCopy.next;
    	    }
    	}
    
    }
    
    ############
    
    /**
     * 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 d1 = new ListNode();
            ListNode d2 = new ListNode();
            ListNode t1 = d1, t2 = d2;
            while (head != null) {
                if (head.val < x) {
                    t1.next = head;
                    t1 = t1.next;
                } else {
                    t2.next = head;
                    t2 = t2.next;
                }
                head = head.next;
            }
            t1.next = d2.next;
            t2.next = null;
            return d1.next;
        }
    }
    
  • // OJ: https://leetcode.com/problems/partition-list/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        ListNode* partition(ListNode* head, int x) {
            ListNode ltHead, geHead, *ltTail = &ltHead, *geTail = &geHead;
            while (head) {
                auto p = head;
                head = head->next;
                if (p->val < x) {
                    ltTail->next = p;
                    ltTail = p;
                } else {
                    geTail->next = p;
                    geTail = p;
                }
            }
            ltTail->next = geHead.next;
            geTail->next = NULL;
            return ltHead.next;
        }
    };
    
  • # 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]:
            d1, d2 = ListNode(), ListNode()
            t1, t2 = d1, d2
            while head:
                if head.val < x:
                    t1.next = head
                    t1 = t1.next
                else:
                    t2.next = head
                    t2 = t2.next
                head = head.next
            t1.next = d2.next
            t2.next = None
            return d1.next
    
    ############
    
    # 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 is None:
          return None
        dummy = ListNode(-1)
        dummy.next = head
        sHead = sDummy = ListNode(-1)
        p = dummy
        while p and p.next:
          if p.next.val < x:
            sDummy.next = p.next
            p.next = p.next.next
            sDummy = sDummy.next
          else:
            p = p.next
          # if you change p.next then make sure you wouldn't change p in next run
        sDummy.next = dummy.next
        return sHead.next
    
    
  • /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func partition(head *ListNode, x int) *ListNode {
    	d1, d2 := &ListNode{}, &ListNode{}
    	t1, t2 := d1, d2
    	for head != nil {
    		if head.Val < x {
    			t1.Next = head
    			t1 = t1.Next
    		} else {
    			t2.Next = head
    			t2 = t2.Next
    		}
    		head = head.Next
    	}
    	t1.Next = d2.Next
    	t2.Next = nil
    	return d1.Next
    }
    
  • /**
     * Definition for singly-linked list.
     * function ListNode(val, next) {
     *     this.val = (val===undefined ? 0 : val)
     *     this.next = (next===undefined ? null : next)
     * }
     */
    /**
     * @param {ListNode} head
     * @param {number} x
     * @return {ListNode}
     */
    var partition = function (head, x) {
        const d1 = new ListNode();
        const d2 = new ListNode();
        let t1 = d1,
            t2 = d2;
        while (head) {
            if (head.val < x) {
                t1.next = head;
                t1 = t1.next;
            } else {
                t2.next = head;
                t2 = t2.next;
            }
            head = head.next;
        }
        t1.next = d2.next;
        t2.next = null;
        return d1.next;
    };
    
    

All Problems

All Solutions