C#•4w ago

Studying singly linked lists and need help understanding pointer functionality

I would love some help understanding something in the following leetcode problem Merge Two Sorted Lists:

void Main()
{
    var list1 = new ListNode(1, new ListNode(2, new ListNode(4, null)));
    var list2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
    
    MergeTwoLists(list1, list2).Dump();    // expected output: [ 1, 1, 2, 3, 4 ]
}

public class ListNode
{
    public int val;
    public ListNode next;
    
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public ListNode MergeTwoLists(ListNode list1, ListNode list2)
{
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    
    ListNode dummy = new();
    ListNode current = dummy;
    
    while (list1 != null && list2 != null)
    {
        int value = 0;
        
        if (list1.val <= list2.val)
        {
            value = list1.val;
            list1 = list1.next;
        }
        else
        {
            value = list2.val;
            list2 = list2.next;
        }
        
        ListNode temp = new(value);
        current.next = temp;      // This modifies dummy...
        current = current.next;   // This does not...
    }

    if (list1 == null) current.next = list2;
    else if (list2 == null) current.next = list1;
    
    return dummy.next;
}

void Main()
{
    var list1 = new ListNode(1, new ListNode(2, new ListNode(4, null)));
    var list2 = new ListNode(1, new ListNode(3, new ListNode(4, null)));
    
    MergeTwoLists(list1, list2).Dump();    // expected output: [ 1, 1, 2, 3, 4 ]
}

public class ListNode
{
    public int val;
    public ListNode next;
    
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public ListNode MergeTwoLists(ListNode list1, ListNode list2)
{
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    
    ListNode dummy = new();
    ListNode current = dummy;
    
    while (list1 != null && list2 != null)
    {
        int value = 0;
        
        if (list1.val <= list2.val)
        {
            value = list1.val;
            list1 = list1.next;
        }
        else
        {
            value = list2.val;
            list2 = list2.next;
        }
        
        ListNode temp = new(value);
        current.next = temp;      // This modifies dummy...
        current = current.next;   // This does not...
    }

    if (list1 == null) current.next = list2;
    else if (list2 == null) current.next = list1;
    
    return dummy.next;
}

When debugging the solution, I can see that during the while loop that setting the pointer current.next = temp modifies dummy.next to equal the temp ListNode. However, setting the pointer current = current.next does not modify dummy. Why is that?

12 Replies

Jimmacle•4w ago

well, why would it? you're making the current variable reference a different object, not changing any object itself

Wrenpo•4w ago

I guess what is breaking my brain is the following: - I set current = dummy (current is now the object dummy instead of just a copy) - I set current.next = temp (dummy.next now equals temp and so does current.next) - I set current = temp (why does temp not replace dummy as a whole since setting current.next changes dummy.next?)

blueberriesiftheywerecats•4w ago

when you have current = dummy you have 2 pointers in the stack that point to the same memory in the heap. that next property is stored in that same memory in the heap thats why you can alter it with current and dummy itself

Wrenpo•4w ago

I think I am following. I am guessing that current and dummy are stored in different memory and that's why changing one does not overwrite the other. With dummy being initialized to a val = 0 from the ListNode constructor, why does dummy not keep that val when creating the chained nodes?

blueberriesiftheywerecats•4w ago

current and dummy are just pointers with the same value(address) when you change current to other node you just change its value(address) not the data behind that address

Wrenpo•4w ago

What documentation can I look up to learn more about this? When doing searches around variables, pass-by-value, pointers, addresses, I get thrown a lot of info about pointers in the literal sense like int* ptr.

blueberriesiftheywerecats•4w ago

the best way to learn about them is by working with them in c/c++

Wrenpo•4w ago

So I guess the following would be true if my understanding is correct:

Car myCar = new ();
Car newCar = myCar; // references the same memory as myCar
newCar.IsRunning = true // myCar and newCar's .IsRunning property change to true
newCar = null // or if set to a new object, only newCar changes but not the myCar object

Car myCar = new ();
Car newCar = myCar; // references the same memory as myCar
newCar.IsRunning = true // myCar and newCar's .IsRunning property change to true
newCar = null // or if set to a new object, only newCar changes but not the myCar object

Basically, if I change the new object that references the previous object to a new object or null, only the new object changes. However, in the original code block, during the while loop, current.Next still updates the links between the nodes. Is this because the property is the same as the object?

blueberriesiftheywerecats•4w ago

next property is inside that allocated memory in the heap, so current.Next and dummy.Next are working with the same object(pointer to the object)

Wrenpo•4w ago

Car and ListNode are objects and go on the heap, including their properties. The local variables myCar, newCar, dummy, and current are on the stack. When I code current.next or myCar.IsRunning, I am referring to the heap object and not the local variable? aka:

int x = 5; // x is a local variable and is stored on the stack

// y is a reference to an object and is stored on the stack
// the object itself is stored on the heap
string y = new string("hello");

// z is a reference to the same object as y
// both y and z are stored on the stack, but the object is only stored once on the heap
string z = y;

// the object referenced by y and z is no longer needed, so the garbage collector will deallocate the memory on the heap
y = null;
z = null;

int x = 5; // x is a local variable and is stored on the stack

// y is a reference to an object and is stored on the stack
// the object itself is stored on the heap
string y = new string("hello");

// z is a reference to the same object as y
// both y and z are stored on the stack, but the object is only stored once on the heap
string z = y;

// the object referenced by y and z is no longer needed, so the garbage collector will deallocate the memory on the heap
y = null;
z = null;

blueberriesiftheywerecats•4w ago

yes

Wrenpo•4w ago

Thanks. Everytime I have come across pass by reference or pass by value or stack vs heap, I feel like a novice all over again. It's like one hurdle I never conquered.

Gaming

Programming

Studying singly linked lists and need help understanding pointer functionality