Skip to content

Instantly share code, notes, and snippets.

@joshparkerj
Created April 8, 2021 03:48
Show Gist options
  • Save joshparkerj/747a2b0eb6a4bf6dd0cd647cd2e255a3 to your computer and use it in GitHub Desktop.
Save joshparkerj/747a2b0eb6a4bf6dd0cd647cd2e255a3 to your computer and use it in GitHub Desktop.
This is what I came up with for partition list during the V&V session April 7
/**
* 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, pivot) {
// create two new linked lists by initializing references for the head and tail of each
var smaller = {};
var larger = {};
// one will be for nodes with values less than the pivot
// call it smaller
// one will be for nodes with values greater than or equal to the pivot
// call it larger.
// process each node by first making a copy
// then compare its value to the pivot
while (head !== null) {
var temp = head.next;
var copy = new ListNode(head.val, head.next);
if (copy.val < pivot) {
addNodeToList(copy, smaller);
} else {
addNodeToList(copy, larger);
}
head = temp;
}
// pass the node to add node to list, along with the smaller list if the value is less than pivot
// or along with the larger list if the value is greater than pivot
// after all nodes are processed, set the smaller tail next to the larger head
// return the smaller head.
larger.tail.next = null;
smaller.tail.next = larger.head;
return smaller.head;
};
var addNodeToList = function(node, list) {
// if the head reference is uninitialized set it to the node
if (!list.head) {
list.head = node;
}
// if the tail reference has been initialized set its next reference to the node
if (list.tail) {
list.tail.next = node;
}
// set the tail reference to the node
list.tail = node;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment