|
CloneListWithRandomNode |
Tests |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class CloneListWithRandomNode public
static class RandomNodeT
{
public T data;pre data-role="codeBlock" data-info="js" cla ss="language-javascript"> public RandomNodeT next;pre data-r ole="codeBlock" data-info="js" class="language-javascript"> public RandomNodeT random;> public RandomNode(T data)pre data-role="codeBlock" data-info="js" class="langu age-javascript"> {> this.data = data;> } > { > if (this == o) return true; > if (o == null || getClass() != o.getClass()) return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> RandomNode? that = (RandomNode?) o; return
Objects.equals(data, that.data);
}
>pre data-role="codeBlock" data-i nfo="js" class="language-javascript"> @Override> public int hashCode()> { > return Objects.hash(data);> } }
> staticT RandomNodeT clone(RandomNodeT original) {> MapRandomNodeT, RandomNodeT map = new
HashMap();
pre data- role="codeBlock" data-info="js" class="language-javascript"> RandomNodeT newHead = null;> RandomNodeT newTail = null;> RandomNodeT current = original; > while(current != null)> { > RandomNodeT copy = new RandomNode(current.data);> if(newHead == null)> {pre data-role="codeBlock" data-info="js" class="language-javascript"> newHead = newTail = copy;pre data-role="codeBlock" data-info="js" class="language-javascri pt"> }pre data-role="codeBlock" data-info="js" class="language-jav ascript"> else> {> newTail.next = copy;> newTail = copy;> }>
map.put(cur
rent, copy);
current =
current.next;
}> > for(Map.EntryRandomNodeT, RandomNodeT e : map.entrySet()) {> RandomNodeT org = e.getKey();>
if(org.random != null)> {> RandomNodeT randomKey = map.get(org.random);
> RandomNodeT randomValue =
map.get(randomKey);
e.getValue().random = randomValue;
}
}> > return newHead;> } } |
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()
RandomNodeInteger rn1 = new RandomNode(1);> RandomNodeInteger rn2 = new
RandomNode(2);> RandomNodeInteger rn3 = new
RandomNode(3);
RandomNodeInteger rn4 = new RandomNode(4);> RandomNodeInteger rn5 = new
RandomNode(5);> rn1.next = rn2; rn2.next = rn3; rn3.next = rn4;
rn4.next = rn5;
rn1.random = rn3;
rn2.random = rn4;
RandomNodeInteger newList = clone(rn1);> boo
lean check = newList.data == 1;> if(!check)
{
> return false;> }> check = newList.random.data == 3;pre data-role="codeBlock" data-info="js" class="language-javas cript"> if(!check)
{
return false;> }> check = newList.next.data == 2; > if(!che ck)
{
> return false;pre data-role="codeBlock" data-info="js" cla ss="language-javascript"> }> check = newList.next.random.data == 4;> if(!check)
{
return false;> }> return true; }
|
DeleteDups
< /tr> Tests
List.NodeInteger runner = head;> while(runner.next != null)> { > if(head.data == runner.next.data)> {> runner.next = runner.next.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }> else> { > runner = runner.next;> }> }head = head.next;}>}data-syntaxhighlighter-params="brus h: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()pre data-role="codeBlock" data-info="js" class="language-javascript"ListInteger list = new List();pre data-role="codeBlock" data-info="js" class="language-javascript"> list.add(1, 2, 3, 1, 2, 4, 3, 1);pre data-role="codeBlock" data-info="js" class="language-javascript"> deleteDups(list.head);pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = list.head.data == 1;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> check = list.head.next.data == 2;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){> return false;pre data-r ole="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> check = list.head.next.next.data == 3;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> check = list.head.next.next.next.data == 4;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {return false;> }pre data-role="codeBlock" data-info="js" class="language-javascript"> return true;pre data-role="codeBlock" data-info="js" class ="language-javascript">}
DeleteEveryOther
Tests
data-syntaxhighl ighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT void deleteEveryOther(List.NodeT head)pre data-role="codeBlock" data-info="js" class="language-javascript"pre data-role="codeBlock" data-info="js" class="language-javascript"> while(head != null && head.next != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> head.next = head.next.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> hea d = head.next;pre data-role="codeBlock" data-info="js" class="lang uage-javascript"> }}ListInteger list = new List();> list.add(1, 2, 3, 4, 5, 6);> deleteEveryOther(list.head);> List.NodeInteger[] result = list.toArray(list.head.getClass(), 3); > int[] a = Arrays.stream(result).mapToInt(x - x.data).toArray();boolean check = Arrays.equals(new int[] {1, 3, 5}, a);if(!check){> return false;> }> return true;}
< /colgroup> < tr style='page-break-inside:avoid'> DoubleList
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>public class DoubleList&l t;Tpre data-role="codeBlock" data-info="js" class="language-javascript"public static class DoubleNodeT{public T data;pre data-role="codeBlock" data-info="js" class="language-javascript"> public DoubleNodeT next;pre data-role="codeBlock" data-info="js" class="language-javascript"> public DoubleNodeT prev;pre data-role="codeBlock" data-info="js" class="language-javascript"> pre data-role="codeBlock" data-info="js" class="language-javascript"> public DoubleNode(T data)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> this.data = data;pre data-role="codeBlock" data-info="js" class ="language-javascript"> }}pre data-role="codeBlock" data-info="js" class="language-javascript"> public DoubleNodeT head;pre data-role="codeBlock" data-info="js" class="language-java script"> public DoubleNodeT tail;pre data-role="codeBlock" data-info="js" class="lan guage-javascript"> pre data-role="codeBlock" data-info="js" class="language-javascript" > public void append(DoubleNodeT node)pre data-role="codeBlock" data-info="js" class="language-j avascript"> {pre data-role="codeBlock" data-info="js" class= "language-javascript"> if(head == null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> head = tail = node;pre data-role="codeBlock" data-info="js" class="lang uage-javascript"> }else{pre data-role="codeBlock" data-info="js" class="language-javascript"> node.prev = tail;pre data-role="codeBlock" data-info="js" class="language-javascript"> tail.next = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> tail = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }}pre data-role="codeBlock" data-info="js" class="language-javascript"> public void prepend(DoubleNodeT node)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> if(head == null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> head = tail = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }else{pre data-role="codeBlock" data-info="js" class="language-javascript"> node.next = head;pre data-role="codeBlock" data-info="js" class="language-javascript"> head.prev = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> head = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }}pre data-role="codeBlock" data-info="js" class="language-javascript"> public void insertBefore(DoubleNodeT before, DoubleNodeT node){pre data-role="codeBlock" data-info="js" class="language-javascript"> if(head == null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> head = tail = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }else{pre data-role="codeBlock" data-info="js" class="language-javascript"> DoubleNodeT runner = head;pre data-role="codeBlock" data- info="js" class="language-javascript"> while(runner != before && runner != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> runner = runner.next;pre data-role="codeBlock" data-info="js" class="language-java script"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> if(runner == null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> tail.next = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> tail = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> elsepre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> before.prev.next = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> node.prev = before.prev;pre data-role="codeBlock" data-info="js" class="language-javascript"> node.next = before;pre data-role="codeBlock" data-info="js" class="language-javascript"> before.prev = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pr e data-role="codeBlock" data-info="js" class="language-javascript"> }}pre data-role="codeBlock" data-info="js" class="language-javascript"> public void insertAfter(DoubleNodeT after, DoubleNodeT node){pre data-role="codeBlock" data-info="js" class="language-javascript"> if(head == null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> head = tail = node;pre data-role="codeBlock" data-info="js" class ="language-javascript"> }else{pre data-role="codeBlock" data-info="js" class="language-javascript"> DoubleNodeT runner = head;pre data-role="codeBlock" data-info="js" class="language-java script"> while(runner != after && runner != null)pre data-role="codeBlock" data-info ="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> runner = runner.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript">if(runner = = null){pre data-role="codeBlock" data-info="js" class="language-javascript"> tail.next = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> tail = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> elsepre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> after.next.prev = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> node.next = after.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> node.prev = after;pre data-role="codeBlock" data-info="js" class="language-javascript"> after.next = node;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> }}}
FindMiddle
Tests
fast = fast.next.next;> }> if(fast == null)pre data-role="codeBlock" data-info="js" class="language-javascri pt"> {pre data-role="codeBlock" data-info="js" class= "language-javascript"> // even number of elements> return (slow.data + slow.next.data) / 2.0;}> return slo w.data;>}data- syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()pre data-role="codeBlock" data-info="js" class="language-javascript"ListInteger l1 = new List&l t;();pre data-role="codeBlock" data-info="js" class="language-javascript"> l1.add(1, 2, 3, 4, 5, 6);pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = midPointAverage(l1.head) == 3.5;pre data-role="codeBlock" data-in fo="js" class="language-javascript"> if(!check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {return false;}pre data-role="codeBlock" data-info="js" class="language-javascript"> ListInteger l2 = new List();l2.add(1, 2, 3, 4, 5, 6, 7);pre data-role="codeBlock" data-info="js" class="language-javascript"> check = midPointAverage(l2.head) == 4;pre data-role="codeBlock" data-info="js" cl ass="language-javascript"> if(!check)pre data-role="codeBlock" data-info=" js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> }return true;}
FlattenDownNode
Tests
> public T data;> public DownNodeT down;public DownNodeT next;> public DownNode(T data)pre data-role="codeBlock" data-info="js" class ="language-javascript"> {pre data-role="codeBlock" data-info="js" class= "language-javascript"> this.data = data;> }}> >staticT void flatten(DownNodeT head) > while(head != null)pre data-role="codeBlock" data-info="js" class ="language-javascript"> {DownNodeT down = head.down;if(down != null){pre data-role="codeBlock" data-info="js " class="language-javascript"> DownNodeT temp = head.next;> while(down.next != null)pre data-r ole="codeBlock" data-info="js" class="language-javascript"> {> down = down.next; > }> head.next = head.down;> down.next = temp;> }head = head.next ;}>}DownNodeInteger n11 = new DownNode(11);> DownNodeInteger n12 = new DownNode(12); pre data-role="codeBlock" data-info="js" class="language-javascript"> DownNodeInteger n13 = new DownNode(13);> DownNodeInteger n21 = new DownNode(21);DownNodeInteger n22 = new DownNode(22);DownNodeInteger n23 = new DownNode(23);DownNodeInteger n31 = new D ownNode(31);> DownNodeInteger n41 = new DownNode(41);> DownNodeInteger n42 = new DownNode(42);> n11.next = n12; n12.next = n13;pre data-role="codeBlock" data-info="js" cl ass="language-javascript"> n12.down = n21; n21.next = n22; n22.next = n23;> n22.down = n31;pre data-r ole="codeBlock" data-info="js" class="language-javascript"> n31.down = n41;> n41.next = n42;> flatten (n11);pre data-role="codeBlock" data-info="js" class="lang uage-javascript"> DownNodeInteger head = n11;> boolean check = head.data == 11;> if(!check){return false;> }> DownNodeInteger next = head.next;> check = next.data == 12;> if(!check){return false;> }> next = next.next;> check = next.data == 21;> if(!check){return false;> }> next = next.next;> check = next.data == 22;> if(!check){return false;> }> next = next.next;> check = next.data == 31;> if(!check){return false;> }> next = next.next;> check = next.data == 41;pre data-role="codeBlock" data-info="js" class ="language-javascript"> if(!check){return false;> }> nex t = next.next;pre data-role="codeBlock" data-info="js" class="l anguage-javascript"> check = next.data == 42;pre data-role="codeBlock" data-info="js" class= "language-javascript"> if(!check){return false;> }> next = next.next;> check = next.data == 23;> if(!check){return false;> }> next = next .next;pre data-role="codeBlock" data-info="js" class= "language-javascript"> check = next.data == 13;> if(!check){> return false;pre data-r ole="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language -javascript"> return true;}
Intersection
Tests
data-sy ntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT List.NodeT intersection(List.NodeT n1, List.NodeT n2)pre data-role="codeBlock" data-info="js" class="language-javascript"> int len1 = length(n1);pre data-role="codeBlock" data-info="js" class="language-javascript"> int len2 = length(n2);pre data-role="codeBlock" data-info="js" class="language-javascript"> for(; len1 len2; len1--)pre data-role="codeBlock" data-info="js" class="language-javascript"> {n1 = n1.next;}pre data-role="codeBlock" data-info="js" class="language-javascript"> for(; len2 len1; len2--)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> n2 = n2.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }while(n1 != null){pre data-role="codeBlock" data-info="js" class="language-javascript"> if(n1 == n2)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> return n1;pre data-role="codeBlock" data-info="js" class="language-javascript"> }n1 = n1.next;n2 = n2.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> return null;}List.NodeInteger a1 = new List.Node(1);> List.NodeInteger a2 = new List.Node(3);> List.NodeInteger a3 = new List.Node(5);pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeInteger a4 = new List.Node(7);> List.NodeInteger a5 = new List.Node (9);> a1.next = a2; a2.next = a3; a3.next = a4; a4.next = a5;> List.NodeInteger b1 = new List.Node(2);> List.NodeInteger b2 = new List.Node(4);List.Node Integer b3 = new List.Node(6);pre data-role="codeBlock" data-info="js" class="language-javas cript"> a1.next = a2; a2.next = a3; a3.next = a4; a4.next = a5;pre data-role="codeBlock" data-info="js" class="language-javascript "> b1.next = b2; b2.next = b3; b3.next = a4;> boolean check = intersection(a1, b1) == a4;> if(!check)pre data-role="codeBlock" data-info="js " class="language-javascript"> {> return false;pre data-role="codeBlock" data-info="js" class="langu age-javascript"> }return true;}
List
Tests
public static class NodeT{> public T data;> public NodeT next;> public Node(T data) > {> this.data = data;> }}>pre data-role="codeBlock" data-i nfo="js" class="language-javascript"> public NodeT head;> public NodeT tail;>public void add(T... data){> for(T t : data)> {pre data-role="codeBlock" data-info="js" class= "language-javascript"> add(t);> }}> public ListT add(T data)> {> return add(new NodeT(data)); > }> {> head = tail = node;> }public ListT add(NodeT node){> if(head == null)else{> if(node.next == null)> {> tail.next = node; > tail = node;> }> else> {> NodeT last = node;> while(last.next != null)> {> last = last.next; > }> tail.next = node;> tail = last;pre data-role="codeBlock" data-info="js" class ="language-javascript"> }> }>public staticT extends ComparableT NodeT[] toArray(NodeT head)> {int len = length(head);NodeT[] result = (NodeT[])Array.newInstance(head.getClass(), len);>NodeT current = head;int idx = 0;while(current != null)pre data-role=" codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-ja vascript"> result[idx++] = current;> current = current.next;> }return result;> }> > NodeT[] toArray(Class? type, int size)> {pre data-role="codeBlock" data-info="js" class="langua ge-javascript"> NodeT[] a = (NodeT[])Array.newInstance(type, size);pre data-role="codeBlock" data-inf o="js" class="language-javascript"> NodeT current = head;pre data-role="codeBlock" data-info="js" class="lang uage-javascript"> int idx = 0;> while(current != null)> {> a[idx++] = current;> current = current.next;pre data-role="codeBlock" data-info="js" class ="language-javascript"> }return a;}> > pub lic staticT int length(NodeT node)> {pre data-role="codeBlock" data-info="js" class= "language-javascript"> int len = 0;> NodeT current = node;> while(current != null)> {> len++;pre data-role="codeBlock" data-info="js" class="language-javascript "> current = current.next;> }return len;}> > public int length()> {return length(head);}pre data-role= "codeBlock" data-info="js" class="language-javascript">}Node& lt;Integer n1 = new Node(1);> NodeInteger n2 = new Node(2);pre data-role="codeBlock" data-info="js" class="language-javascript"> NodeInteger n3 = new Node(3);pre data-role="codeBlock" data-info="js " class="language-javascript"> ListInteger list1 = new List();> list1.add(n1).add(n2).add(n3);pre data-role="codeBlock" data-info="js" class="language-javascript"> boolean check = list1.head.data == n1.data;if(!check)> { pre data-role="codeBlock" data-info="js" class=" language-javascript"> return false;> }check = list1.tail.data == n3.data;> if(!check){> return false;> }check = list1.head.next.data == n2.data;if(!check){> return false;> }> NodeInteger n4 = new Node(4);pre data-role="codeBlock" data-info="js" class="language-javascript"> NodeInteger n5 = new Node(5);> NodeInteger n6 = new Node(6);n5.next = n6;> ListInteger list2 = new List();> list2.add(n4); > check = list2.head.data == n4.data;> if(!check)> {return false;}> check = list2.tail.data == n4.data;> if(!check)> {> return false; > }list2.add(n5);check = list2.head.next.data == n5.data;if(!check){> return false;> }pre data-role="codeBlock" data-info="js" class ="language-javascript"> check = list2.tail.data == n6.data;> if(!check){return false;pre data-role="codeBlock" data-info="js " class="language-javascript"> }> check = n4.next.data == n5.data;> if(!check){> return false;> }> check = list2.length() == 3;> if(!check){return false;pre data-role="codeBlock" data-info="js" class= "language-javascript"> }> retu rn true;}
< col style="width: 771.0px;"> ListToNumber
Tests
data- syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int addNumbersFromReversedLists(ListInteger l1, ListInteger l2)pre data-role="codeBlock" data-info="js" class="language-javascript"pre data-role="codeBlock" data-info="js" class="language-javascript"> Lis tInteger result = new List();pre data-role="codeBlock" data-info="js" class=" language-javascript"> List.NodeInteger n1 = l1.head;pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeInteger n2 = l2.head;pre data-role="codeBlock" data-info="js" class="language-javascript"> int carry = 0;pre data-role="codeBlock" data-info="js" class="language-javascript"> while(n1 != null && n2 != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {int sum = n1.data + n2.data + carry;int val = sum % 10;> carry = sum / 10;> result.add(val);pre data-role="codeBlock" data-info="js" class="language-javascript"> n1 = n1.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> n2 = n2.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }List.NodeInteger n = n1 != null ? n1 : n2;pre data-role="codeBlock" data-info="js" class="language-javascript"> while(n != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {int sum = n1.data + carry;int val = sum % 10;carry = sum / 10;pre data-role="codeBlock" data-info="js" class="language-javascript"> result.add(val);pre data-role="codeBlock" data-info="js" class="language-javascript"> n = n.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }if(carry 0){pre data-role="codeBlock" data-info="js" class="language-javascript"> result.add(carry);pre data-role="codeBlock" data-info="js" class="language-javascript"> }int sum = 0;int power = 0;pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeInteger current = result.head;while(current != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> sum += (int)Math.pow(10, power++) * current.data;pre data-role="codeBlock" data-info="js" class="language-javascript"> current = current.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }return sum;}data- syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static int addNumbersFromLists(ListInteger l1, ListInteger l2)pre data-role="codeBlock" data-info="js" class="language-javascript"pre data-role="codeBlock" data-info="js" class="language-javascript"> return listToNumber(l1) + listToNumber(l2);pre data-role="codeBlock" data-info="js" class="language-jav ascript">}pre data-role="codeBlock" data-info="js" class="language-javascript">pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> val = 10 * val + current.data;pre data-role="codeBlock" data-info="js" class="language-javascript"> current = current.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }private static int listToNumber(ListInteger li st)List.NodeInteger current = list.head;int val = 0;pre data-role="codeBlock" data-info="js" cl ass="language-javascript"> while(current != null)return val;< /pre>}ListInteger l1 = new List(), l2 = new List();> l1.add(5).add(4).add(3);> l2.add(7).add(6);> boolean check = addNumbersFromReversedLists(l1, l2) == 412;> if(!check)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class ="language-javascript"> return false;> }check = addNumbersFromLists(l1, l2) == 619;if(!check)> {pre data-role="codeBlock" data-info="j s" class="language-javascript"> return false;pre data-role="codeBlock" data-i nfo="js" class="language-javascript"> }> return true;}
MergeSorted
Tests
data- syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static ListInteger mergeSorted(List.NodeInteger n1, List.NodeInteger n2)pre data-role="codeBlock" data-info="js" class="language-java script"> ListInteger result = new List();pre data-role="codeBlo ck" data-info="js" class="language-javascript"> while(n1 != null && n2 != null)pre data-r ole="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javasc ript"> List.NodeInteger n;pre data-role="codeBlock" data-info="js" class="language-javascript"> if(n1.data n2.data)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> n = new List.Node(n1.data);pre data-role="codeBlock" data-info="js" class= "language-javascript"> n1 = n1.next;pre data-role="codeBlock" data-info="js" class= "language-javascript"> }else{pre data-role="codeBlock" data-info="js" class="language-javascript"> n = new List.Node(n2.data);pre data-role="codeBlock" data-info="js" cl ass="language-javascript"> n2 = n2.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class= "language-javascript"> result.add(n);pre data-role="codeBlock" data-info="js" class="language-javascript"> }if(n1 != null) result.add(n1);if(n2 != null) result.add(n2);> return result;pre data-role="codeBlock" data-info="js" class="language-javascript">}data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()pre data-role="codeBlock" data-info="js" class="language-javascript"ListInteger l1 = new List(), l2 = new List();pre data-role="codeBlock" data-info="js" class="language-javascript"> l1.add(1, 3, 5);pre data-role="codeBlock" data-info="js" class="language-javascript"> l2.add(2, 4, 6, 8);pre data-role="codeBlock" data-info="js" class="language-javascript"> ListInteger sortedList = mergeSorted(l1.head, l2.head);pre data-role="codeBlock" data-info="js" cla ss="language-javascript"> List.NodeInteger[] nodes = sortedList.toArray(l1.head.get Class(), sortedList.length());pre data-role="codeBlock" data-info="js" class="language-javascript"> int[] ints = Arrays.stream(nodes).mapToInt(x - x.data).toArray();pre data-r ole="codeBlock" data-info="js" class="language-javascript"> Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 8}, ints);boolean check = Arrays.equals(new int[] {1, 2, 3, 4, 5, 6, 8}, ints);if(!check){pre data-role="codeBlock" data-info="js" class="language-javascript"> return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> return true ;}
MinInCicrular
< /tr> Tests
min = Math.min(min, start.data);start = start.next;}> return min;>}List.NodeInteger n1 = new List.Node(1);> List.NodeInteger n2 = new List.Node(0);> List.NodeInteger n3 = new List.Node(5);> List.NodeInteger n4 = new List.Node(3);List.NodeInteger n5 = new List.Node(7);> List.NodeInteger n6 = new List.Node(9);> List.NodeInteger n7 = new List.Node(-3);pre data- role="codeBlock" data-info="js" class="language-javascript"> n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5; n5.next = n6; n6.next = n7; n7.next = n1;> boolean check = minInCircular(n1) == -3;pre data-role="codeBlock" data-info="js" class= "language-javascript"> if(!check){return false;> }> return true;}
NthToLast
Tests
data-syntaxhighlighter -params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT extends ComparableT List.NodeT nthToLast(List.NodeT head, int n)pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeT curent = head, runner = head;pre data-role="codeBlock" data-info="js" class="language-javascript"> for(int i = 0; i n; ++i)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> if (runner != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> runner = runner.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }}if(runner == null)pre data- role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> return null;pre data-role="codeBlock" data-info="js" class="language-javascript"> }while(runner != null)> {pre data-role="codeBlock" data-info="js" class="language-javascript"> curent = curent.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> runner = runner.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> return curent;pre data-role="codeBlock" data-info="js" class="language-javascript">}> List< ;Integer list = new List();> list.add(1, 2, 3, 4, 5, 6, 7);> List.NodeInteg er n = nthToLast(list.head, 2);> boolean check = n.data == 6;> if(!check)> {return false;}> return true;>}
PairwiseSwap
Tests
data-syntaxhighlighter-params="brush: ja va; gutter: false; theme: Confluence" data-t heme=Confluence>staticT void pairwiseSwap(List.NodeT head)pre data-role="codeBlock" data-info="js" class="language-javascript"pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeT current = head;pre data-role="codeBlock" data-info="js" class="language-javascript"> while(current != null && current.next != null)pre data-role="codeBlock" data-info="js" class="language-javascript"> {pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeT nextNode = current.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> T temp = nextNode.data;pre data-role="codeBlock" data-info="js" class="language-javascript"> nextNode.data = current.data;pre data-role="codeBlock" data-info="js" class="language-javascript"> current.data = temp;pre data-role="codeBlock" data-info="js" class="language-javascript"> current = current.next.next;pre data-role="codeBlock" data-info="js" class="language-javascript"> }}ListInteger list = new List();> list.add(1, 2, 3, 4, 5, 6);> pairwiseSwap(list.head);> List.NodeInteger[] result = list.toArray(list.head.getClass(), 6);> int[] a = Arrays.stream(result).mapToInt(x - x.data).toArray();boolean check = Arrays.equals(new int[] {2, 1, 4, 3, 6, 5}, a);pre data-role="codeBlock" data-info="js" class="la nguage-javascript"> if(!check){return false;> }> return true;}
Reverse
< /tr> < tr style='page-break-inside:avoid'> Tests
> List.NodeInteger next = current.next;> current.next = prev;> prev = current; > current = next;pre data-role="codeBlock" data-info="js" class ="language-javascript"> }return prev;}data-syntaxhighlighter-params="brush: ja va; gutter: false; theme: Confluence" data-theme=Confluence>static boolean testsPass()pre data-role="codeBlock" data-info="js" class= "language-javascript"ListInteger list = new List();pre data-role="codeBlock" data-info="js" class="language-javascript"> list.add(1, 2, 3, 4, 5);pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeInteger reversed = reverse(list.head);pre data-role="codeBlock" data-info="js" class="language-javascript"> List.NodeInteger[] arr = toArray(reversed);pre data-role="codeBlock" data-info="js" cl ass="language-javascript"> int[] a = Arrays.stream(arr).mapToInt(x - x.data).toArray();boolean check = Arrays.equals(new int[] {5, 4, 3, 2, 1}, a);pre data-role="codeBlock" data-info="js" class="language-javascript"> if(!check){return false;pre data-role="codeBlock" data-info="js" class="language-javascript"> }pre data-role="codeBlock" data-info="js" class="language-javascript"> return true;}
< colgroup>
StartOfLoop
Tests
data-syntaxhighlighter-params="brush: java; gutter: false; theme: Confluence" data-theme=Confluence>staticT List.NodeT startOfLoop(List.NodeT head)pre data-role="codeB lock" data-info="js" class="language-javascript"> if(head == null || head.next == null)> {return null;}pre data-role="codeBlock" data-info ="js" class="language-javascript"> boolean loopExists = false;> List.NodeT slow = head, fast = head;> while(fast != null && fast.next != null)> fast = fast.ne xt.next;> if(slow == fast)> {> loopExists = true;> break; > }{> slow = slow.next;}if(!loopExists)> {> return null;> }fast = head;while(slow != fast)> {> slow = slow.next;> fast = fast.next;> }return slow;}List.NodeInteger n1 = new List.Node(1);> List.NodeInteger n2 = new List.Node(0);pre data-role="codeBlock" data- info="js" class="language-javascript"> List.NodeInteger n3 = new List.Node(5);> List.NodeInteger n4 = new List.Node(3);> List.N odeInteger n5 = new List.Node(7);> List.NodeInteger n6 = new List.Node(9); > n1.next = n2; n2.next = n3; n3.next = n4; > n4.next = n5; n5.next = n6; n6.next = n2;> boolean check = startOfLoop(n1) == n2;> if(!check)> {return false;> }> return true;pre data-role="codeBlock" data-info="js" class="language-javasc ript">}