Message from @Jacob
Discord ID: 502720369547804672
@ThisIsChris I have a big 4 hour programming test this week, so I'm gonna be preparing for that and should probably put my work on this script on hold for a few days
@Jacob good luck on your exam!
thanks!
```java
/**
*
* Implement the private reverse(ListNode node) method using recursion.
* You are allowed to add helper method into this class if needed.
* @param node -- the reference of the first data node(successor of the dummy) in the original list.
* @return A new MyLinkedList object contains the same set of data items, but in a reversed order.
*/
private MyLinkedList reverse(ListNode node) {
MyLinkedList reversed = new MyLinkedList();
ListNode curr = node;
ListNode lastNode = null;
while (curr != null) {
lastNode = curr;
curr = curr.next;
}
reversed.head.next = lastNode;
if (node.next != null) {
reversed.head.next.next = reverse(node.next).head.next;
}
return reversed; // change this line of code as needed
}
```
Does anyone see anything wrong with this code?
```java
/**
* This method reverse2() will reverse all data nodes in this list, WITHOUT
* creating(introducing) new list nodes, by simply re-wiring the next reference in
* the existing list node. For example, list1 = []ā>[A]ā>[B],
* the reversed list1 will be []-->[B]-->[A],
* after assigning node A to B's next reference and setting A's next to null.
*
*/
public void reverse2() {
if(this.size <= 1)
return;
// The following method call works on a *sublist* without a Dummy Node.
// Namely, we preserved the OLD dummy head node in the reversed list.
this.head.next = reverse(this.head.next, this.head.next.next);
}
/**
* Please implement the helper method below for reverse2().
* @param first, the first node of the list to be reversed.
* @param second, the second node of the list to be reversed.
* @return the new head node of the reversed list.
* Note: you are NOT allowed to create new list node, but have to
* re-wiring the existing nodes by changing their next references.
* Write this method using recursion.
*/
private ListNode reverse(ListNode first, ListNode second) {
ListNode curr = first;
ListNode newFirstNode = null;
ListNode newLastNode = null;
ListNode newHead = new ListNode();
while (curr.next != null) {
newLastNode = curr;
newFirstNode = curr.next;
curr = curr.next.next;
}
newHead.next = newFirstNode;
newLastNode.next = null;
newFirstNode.next = reverse(newFirstNode.next, newFirstNode.next.next);
return newHead; //change this line of code as needed.
}
```
and this ^
I'm honestly not sure what the point of passing the second node is, since (I think) it can be determined from the first node using .next
<@&435155896780324864>
That's all for tonight by the way. I won't spam you guys with a bunch of other methods, it's just these.
@Jacob well it's recursive right, and one node IIRC is a null node, right? null wouldn't have a null.next
ah
you mean at the end?
when the function is originally called, I assume both nodes are fine
but ya I think that makes sense
that at some point second will be null
wait no that shouldn't be an issue
because each Linked List object has a size variable to check for that
wait no that wouldn't work because I'm not actually passing a list
haha yeah that linked list/ tree stuff is tricky, maybe later in the weekend I can focus on it if you're still working on it, hopefully someone else here can help out sooner than that though š <@&387091385075105804> <@&435155896780324864>
```java
/**
* This method reverse2() will reverse all data nodes in this list, WITHOUT
* creating(introducing) new list nodes, by simply re-wiring the next reference in
* the existing list node. For example, list1 = []ā>[A]ā>[B],
* the reversed list1 will be []-->[B]-->[A],
* after assigning node A to B's next reference and setting A's next to null.
*
*/
public void reverse2() {
if(this.size <= 1)
return;
// The following method call works on a *sublist* without a Dummy Node.
// Namely, we preserved the OLD dummy head node in the reversed list.
this.head.next = reverse(this.head.next, this.head.next.next);
}
/**
* Please implement the helper method below for reverse2().
* @param first, the first node of the list to be reversed.
* @param second, the second node of the list to be reversed.
* @return the new head node of the reversed list.
* Note: you are NOT allowed to create new list node, but have to
* re-wiring the existing nodes by changing their next references.
* Write this method using recursion.
*/
private ListNode reverse(ListNode first, ListNode second) {
ListNode newHead = new ListNode();
if (second.next != null) {
ListNode curr = first;
ListNode newFirstNode = null;
ListNode newLastNode = null;
while (curr.next != null) {
newLastNode = curr;
newFirstNode = curr.next;
curr = curr.next.next;
}
newHead.next = newFirstNode;
newLastNode.next = null;
newFirstNode.next = reverse(newFirstNode.next, newFirstNode.next.next);
}
else {
newHead.next = second;
second.next = first;
first.next = null;
}
return newHead; //change this line of code as needed.
}
```
@ThisIsChris okay this is what I have right now, do you think this works?
<@&435155896780324864> In the past week I've been hit up by recruiters 3 times asking if I know how to update a website for Search Engine Optimization (SEO). I don't intend to go into it, but the demand is there and I know this is a field you can get into relatively quickly. Lots of information online to learn from this is a big one https://moz.com/beginners-guide-to-seo
Iām an SEO and Iād love to pick up work if I could. If you need help learning about it or see an offer let me know š
@Gumbo - AZ will do!
<@&435155896780324864> Does anyone know how to do a Big O time complexity analysis on a Java function?
@Jacob example function?
```java
public static void two(int n)
{
if(n > 0)
{
System.out.println("n: " +n);
two(n - 1);
two(n - 1);
}
else if (n < 0)
{
two(n + 1);
two(n + 1);
System.out.println(ā³n: ā³ + n);
}
}
```
It's mostly like doing it on paper, you have most of the same assumptions of the Random Access Machine
Do you have any skepticism that assumptions of RAM don't hold?
No, it's just a basic analysis. I need to provide a "logical justification" for my answer. Not sure if that means I have to write a paragraph or there's some kind of equation I need to use.
There's an equation.
Not necessarily expecting an answer to the question from anyone, but maybe something that can get me in the right direction
f(0) = O(1)
f(|n|) = 2*f(|n|-1) + O(1)
š¬
so f(n) = O(2^n)
Is that the equation for this particular function?
yep
How would I go about getting that?