I have seen similar questions asked, but none of the answers really address my confusion.
I'm working through some Linked List content, trying to write methods to solve leetcode-like problems. I'm working with singly-linked lists, defined as:
public class LinkedListy {
ListNode head;
LinkedListy(){};
public static class ListNode {
int val; //integer variable
ListNode next; //pointer
ListNode() {}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val; this.next = next;
}
}
...
I'm trying to write a function that will reverse my linked list, but will not destroy my original linked list. The code I have written works to reverse the list, but destroys the original list:
public ListNode reverse() {
//use copyList function to avoid altering head --> DOESN'T WORK
ListNode current = head;
ListNode temp = null;
ListNode copied_result = null;
while(current != null){
temp = current.next;
current.next = copied_result;
copied_result = current;
current = temp;
}
return copied_result;
}
From reading on here and other places, I understand that by setting current = head, I'm just creating a new reference for the same ListNode. Thus, when I run my code, I'm mutating the original list.
Main Confusion: I'm confused because I have written methods that do NOT destroy the original list, but use the same kind of reference to head. For example, in my "length()" method, I set dummy = head and alter dummy to find the length of the list. But, then the original list doesn't get changed (I wrote a print function to print the list and I verified it prints the same before and after calling length().)
public int length() {
ListNode dummy = head;
int length = 0;
while(dummy != null) {
dummy = dummy.next;
length++;
}
return length;
}
So, I'm clearly not understanding something fundamental about LinkedLists.
- Why does my reverse() method destroy the original list when my length() method does not?
- Is the only way to write a reverse method for a linked list without destroying the original list to make a copy of the original list in your main method and reverse the copy?
Any help or resources would be greatly appreciated. Thanks!
