Created
April 8, 2021 03:48
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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