C#•13mo ago

❔ Removing dupes in a linked list

I need to make a function that gets a linked list, and returns that linked list with all sequences of 3 or more consecutive equal numbers be removed for example: 1,3,3,3,4,5,5,6,9,9,9,9 becomes 1,4,5,5,6

129 Replies

JakenVeina•13mo ago

$details

MODiX•13mo ago

When you ask a question, make sure you include as much detail as possible. Such as code, the issue you are facing, and what you expect the result to be. Upload code here https://paste.mod.gg/ (see $code for more information on how to paste your code)

MayonaizeOP•13mo ago

well i dont have any code written as i dont have an idea as to were to start sadly thats also my issue

JakenVeina•13mo ago

alright let's break down the problem

MayonaizeOP•13mo ago

I have a very vague idea but no more than that

JakenVeina•13mo ago

gotta start somewhere what is your vague idea?

MayonaizeOP•13mo ago

first thing is

MayonaizeOP•13mo ago

p1 being a pointer on first object p2 on the one after and inside that if clause i would put it into a new list hold on ill write it so its more clear

JakenVeina•13mo ago

so A) your plan is to build a new list, rather than trying to modify the existing one

MayonaizeOP•13mo ago

MayonaizeOP•13mo ago

yeah thats what they want in the question, sorry i didnt specify

JakenVeina•13mo ago

great

MayonaizeOP•13mo ago

although it really doesnt matter since i can make a copy of the old list i have a function for that

JakenVeina•13mo ago

you're allowed to use the built-in LinkedList here, or you have to write your own?

MayonaizeOP•13mo ago

nope we use the one the teacher built i can send you it if you want

JakenVeina•13mo ago

please do $code

MODiX•13mo ago

To post C# code type the following: ```cs // code here ``` Get an example by typing $codegif in chat For longer snippets, use: https://paste.mod.gg/

MayonaizeOP•13mo ago

 public class Node<T>
    {
        private T value;           // Node value
        private Node<T> next;      // next Node

        /* Constructor  - returns a Node with "value" as value and without successesor Node **/
        public Node(T value)
        {
            this.value = value;
            this.next = null;
        }

        /* Constructor  - returns a Node with "value" as value and its successesor is "next" **/
        public Node(T value, Node<T> next)
        {
            this.value = value;
            this.next = next;
        }

        /* Returns the Node "value" **/
        public T GetValue()
        {
            return this.value;
        }

        /* Returns the Node "next" Node **/
        public Node<T> GetNext()
        {
            return this.next;
        }

        /* Return if the current Node Has successor **/
        public bool HasNext()
        {
            return (this.next != null);
        }

        /* Set the value attribute to be "value" **/
        public void SetValue(T value)
        {
            this.value = value;
        }

        /* Set the next attribute to be "next" **/
        public void SetNext(Node<T> next)
        {
            this.next = next;
        }

        /* Returns a string that describes  the Node (and its' successesors **/
        public override string ToString()
        {
            return value + "-->" + next;
           
        }
    }

 public class Node<T>
    {
        private T value;           // Node value
        private Node<T> next;      // next Node

        /* Constructor  - returns a Node with "value" as value and without successesor Node **/
        public Node(T value)
        {
            this.value = value;
            this.next = null;
        }

        /* Constructor  - returns a Node with "value" as value and its successesor is "next" **/
        public Node(T value, Node<T> next)
        {
            this.value = value;
            this.next = next;
        }

        /* Returns the Node "value" **/
        public T GetValue()
        {
            return this.value;
        }

        /* Returns the Node "next" Node **/
        public Node<T> GetNext()
        {
            return this.next;
        }

        /* Return if the current Node Has successor **/
        public bool HasNext()
        {
            return (this.next != null);
        }

        /* Set the value attribute to be "value" **/
        public void SetValue(T value)
        {
            this.value = value;
        }

        /* Set the next attribute to be "next" **/
        public void SetNext(Node<T> next)
        {
            this.next = next;
        }

        /* Returns a string that describes  the Node (and its' successesors **/
        public override string ToString()
        {
            return value + "-->" + next;
           
        }
    }

srry its long

JakenVeina•13mo ago

lovely

MayonaizeOP•13mo ago

very i feel like i need a nested loop here or another function that i build

JakenVeina•13mo ago

possibly there's a variety of ways you could do this let's think about the problem first

MayonaizeOP•13mo ago

Can i tell you the idea i thought of just now with the nested loop ?

JakenVeina•13mo ago

you have to build a list from a set of input numbers

MayonaizeOP•13mo ago

or do you wanna do this first i might have overlooked something well i just like i copied the example it gave me

JakenVeina•13mo ago

right

MayonaizeOP•13mo ago

int[] arr = { 1, 3,3,3,4,5,5,6,9,9,9,9};
            Node<int> list = CreateList(arr);

int[] arr = { 1, 3,3,3,4,5,5,6,9,9,9,9};
            Node<int> list = CreateList(arr);

JakenVeina•13mo ago

where it should ignore any sequences of the same consecutive number, longer than 3 so

MayonaizeOP•13mo ago

yep

JakenVeina•13mo ago

what are you going to need here that you KNOW

MayonaizeOP•13mo ago

ok so definitely a counter

JakenVeina•13mo ago

maybe even more fundamental than that

MayonaizeOP•13mo ago

do you not think so? um

JakenVeina•13mo ago

not sure

MayonaizeOP•13mo ago

while loop?

JakenVeina•13mo ago

some kinda loop, for sure to iterate the input numbers

MayonaizeOP•13mo ago

yeah and to make sure i dont reach null right?

JakenVeina•13mo ago

what does "reach null" mean?

MayonaizeOP•13mo ago

i mean like the list ends at some point

JakenVeina•13mo ago

which list?

MayonaizeOP•13mo ago

any list i gues s i mean like after the 9 it points to null

JakenVeina•13mo ago

nnnno, that array does not have any nulls in it

MayonaizeOP•13mo ago

nonono not the array i create a list with the values from the array i can send you that function as well if you want

JakenVeina•13mo ago

okay, but what does that have to do with what we're talking about

MayonaizeOP•13mo ago

 public static Node<T> CreateList<T>(T[] arr)
        {
            Node<T> n = new Node<T> (arr[0]);
            Node<T> first = n;
            Node<T> p = n;
            for (int i = 1; i < arr.Length; i++)
            {
                n = new Node<T>(arr[i]);
                p.SetNext(n);
                p = p.GetNext();
            }
            return first;
        }

 public static Node<T> CreateList<T>(T[] arr)
        {
            Node<T> n = new Node<T> (arr[0]);
            Node<T> first = n;
            Node<T> p = n;
            for (int i = 1; i < arr.Length; i++)
            {
                n = new Node<T>(arr[i]);
                p.SetNext(n);
                p = p.GetNext();
            }
            return first;
        }

JakenVeina•13mo ago

some kinda loop, for sure to iterate the input numbers

MayonaizeOP•13mo ago

ok yeah i understand why

JakenVeina•13mo ago

there's no nulls involved in iterating the input, if the input is an array

MayonaizeOP•13mo ago

it isnt an array its a linked list

JakenVeina•13mo ago

the input is?

MayonaizeOP•13mo ago

no look here i made a list out of the array and then i call the function on the list

JakenVeina•13mo ago

why?

MayonaizeOP•13mo ago

idk thats what they want me to do

JakenVeina•13mo ago

okay so the input is, in fact, a linked list

MayonaizeOP•13mo ago

JakenVeina•13mo ago

and we are trying to build a new list from that yes?

MayonaizeOP•13mo ago

yeah

JakenVeina•13mo ago

so, again let's start with what we KNOW

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{

}

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{

}

MayonaizeOP•13mo ago

JakenVeina•13mo ago

and then we said, we KNOW we need to at least iterate all the nodes in the input list so go ahead and write that loop

MayonaizeOP•13mo ago

ok so like a while loop or for loop I would do likeeee

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int> iterator = listHead;
    while(listHead !=null)
   {
      iterator = iterator.GetNext();
   }
}

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int> iterator = listHead;
    while(listHead !=null)
   {
      iterator = iterator.GetNext();
   }
}

is that ok or would you do something different

JakenVeina•13mo ago

for clarity, I would recommend A) not modifying input parameters, just in general B) not using a variable named listHead to represent something that isn't the head of a list

MayonaizeOP•13mo ago

so make a copy first?

JakenVeina•13mo ago

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    var currentNode = listHead;
    while(currentNode != null)
    {
       currentNode = currentNode.GetNext();
    }
}

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    var currentNode = listHead;
    while(currentNode != null)
    {
       currentNode = currentNode.GetNext();
    }
}

MayonaizeOP•13mo ago

oh yeah that seems better

JakenVeina•13mo ago

clarifies your intention so what else do we know? about this method

MayonaizeOP•13mo ago

um that we have to compare values ?

JakenVeina•13mo ago

true what else?

MayonaizeOP•13mo ago

ummmmm well i have to create a new list

JakenVeina•13mo ago

even more specifically, we have to return it

MayonaizeOP•13mo ago

oh yeah right so like

JakenVeina•13mo ago

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int>? resultHead = null;

    var currentNode = listHead;
    while(currentNode != null)
    {
       currentNode = currentNode.GetNext();
    }

    return resultHead;
}

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int>? resultHead = null;

    var currentNode = listHead;
    while(currentNode != null)
    {
       currentNode = currentNode.GetNext();
    }

    return resultHead;
}

MayonaizeOP•13mo ago

yeah ok wait what is that question mark

JakenVeina•13mo ago

indicates that the value can be null

MayonaizeOP•13mo ago

wait what does that mean sorry like what if i just do that without ? thats what ive been doing

JakenVeina•13mo ago

what version of .NET/C# are you using?

MayonaizeOP•13mo ago

ummmm i think 4.7.1

JakenVeina•13mo ago

(look at your .csproj)

MayonaizeOP•13mo ago

wait lemme check um\

MayonaizeOP•13mo ago

in here

JakenVeina•13mo ago

close enough you're on .NET Framework

MayonaizeOP•13mo ago

oh yeah

JakenVeina•13mo ago

sigh why do universities insist on teaching people exlusively on out-of-date technology

MayonaizeOP•13mo ago

im in highschool :( and its not my teacher its like the ministry of education

JakenVeina•13mo ago

so, ignore the nullability thing, that was introduced to C# only somewhat recently and it's an optional feature, anyway

MayonaizeOP•13mo ago

kk alr

JakenVeina•13mo ago

so now, we have a basic structure for the method what next?

MayonaizeOP•13mo ago

I would like try to see how we compare the values while putting them into the new list

JakenVeina•13mo ago

compare what values?

MayonaizeOP•13mo ago

well each time we compare different values

JakenVeina•13mo ago

each time what? think about it more fundamentally you have a loop

MayonaizeOP•13mo ago

each iteration we compare 2 different values

JakenVeina•13mo ago

over each item in the input list yeah, what is it that we need to DO within each iteration? so

MayonaizeOP•13mo ago

well a couple of things right?

JakenVeina•13mo ago

each iteration we compare 2 different values

which 2 different values?

MayonaizeOP•13mo ago

um like say the linked list is 1-> 2 ->2->3 then like 1st iteration: 1,2 2nd: 2,2 3rd: 2,3 idk how to put it into words

JakenVeina•13mo ago

so, from the perspective of a single iteration what are we comparing

MayonaizeOP•13mo ago

ummmmmmmm the value of currentNode and the next current node

JakenVeina•13mo ago

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int>? resultHead = null;

    var currentNode = listHead;
    while(currentNode != null)
    {
        // compare 2 values

        currentNode = currentNode.GetNext();
    }

    return resultHead;
}

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
{
    Node<int>? resultHead = null;

    var currentNode = listHead;
    while(currentNode != null)
    {
        // compare 2 values

        currentNode = currentNode.GetNext();
    }

    return resultHead;
}

that'll work you could also consider it "the current node and the previous node"

MayonaizeOP•13mo ago

rightttt that seems better

JakenVeina•13mo ago

maybe both are valid

MayonaizeOP•13mo ago

alr so we add another variable? or do we use current node

JakenVeina•13mo ago

which approach are you going with?

MayonaizeOP•13mo ago

i think ill go with previous and current it seems easier

JakenVeina•13mo ago

so, how do we retrieve the previous node, from the current node?

MayonaizeOP•13mo ago

oh well i guess we cant really

JakenVeina•13mo ago

righto

MayonaizeOP•13mo ago

at least not in this linked list its not an option for us

JakenVeina•13mo ago

not directly, yes

MayonaizeOP•13mo ago

um i have an idea so before the loop we add another variable prevNode hold ill just write it down

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
        {
            var currentNode = listHead;
            var prevNode = currentNode;
            currentNode = currentNode.GetNext();
            while (currentNode != null)
            {
                currentNode = currentNode.GetNext();
                prevNode = currentNode;
            }
            return listHead;
        }

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
        {
            var currentNode = listHead;
            var prevNode = currentNode;
            currentNode = currentNode.GetNext();
            while (currentNode != null)
            {
                currentNode = currentNode.GetNext();
                prevNode = currentNode;
            }
            return listHead;
        }

would this be fine? or is there something better

JakenVeina•13mo ago

well that's wrong, for starters well no that would work assuming you always HAVE a first node NOW it's wrong

MayonaizeOP•13mo ago

like ur saying i might have a list with 1 value? or no values?

JakenVeina•13mo ago

you tell me can those things happen?

MayonaizeOP•13mo ago

well yeah i guess

JakenVeina•13mo ago

how would your code handle it?

MayonaizeOP•13mo ago

crash like not run

JakenVeina•13mo ago

no, not exactly what happens if listHead is null?

MayonaizeOP•13mo ago

then this wouldnt work right?

JakenVeina•13mo ago

yup, that'll throw NullReferenceException

MayonaizeOP•13mo ago

hmmm ok so how do we fix that lemme think

JakenVeina•13mo ago

what if listHead.GetNext() is null?

MayonaizeOP•13mo ago

do we just add an if? well it would run

JakenVeina•13mo ago

you can indeed, it'll run completely fine for a list with 1 item

MayonaizeOP•13mo ago

but it wouldnt even go into the loop

JakenVeina•13mo ago

right I mean, except for the fact that we aren't doing anything to build the new list, yet

MayonaizeOP•13mo ago

well yeah

JakenVeina•13mo ago

I gotta go make dinner, fill me in on your progress when I get back

MayonaizeOP•13mo ago

alr ill try ty i really apprecaite it ooooo i have an idea on how to fix the NullReference thingy

var resultHead = new Node<int>(0, listHead);
var prevNode = resultHead;
var currentNode = listHead;

var resultHead = new Node<int>(0, listHead);
var prevNode = resultHead;
var currentNode = listHead;

and i might have gotten an idea for the nested loop but idk i gotta see first like i wanna use a previous and a next and a current maybe that might work but only initalize the next node in the loop so i can like i wanna use nextNode to iterate inside the loop until the thingy changes then i can change currentnode to next node i also think it might be better to delete thingies cuz idk how to do it otherwise ima try what io have in imnd and come back and like use previous to link the thingies idk how to explainw ith words ok so i think i got it maybe i have a mistake but what i did kinda like links next node and prev node and like if it doesnt i guess i need to change prev current? but only if it doesnt? wait maybe not to next but to current? ok i think i might have got it

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
        {
            var resultHead = new Node<int>(0, listHead);
            var prevNode = resultHead;
            var currentNode = listHead;

            currentNode = currentNode.GetNext();
            while (currentNode != null)
            {
                Node<int> nextNode = currentNode.GetNext();
                int counter = 1;
                while (nextNode != null && currentNode.GetValue() == nextNode.GetValue())
                {
                    counter++;
                    nextNode = nextNode.GetNext();
                }
                if (counter >= 3){prevNode.SetNext(nextNode);}

                else {prevNode = currentNode;}

                currentNode = nextNode;

                currentNode = currentNode.GetNext(); //If nodes get deleted it goes straight to the place after deletion, if not it goes the the place after checking the duplicates.
            }
            return listHead;
        }

public Node<int> DuplicateListWithoutConsecutiveValueSequencesLongerThan2(Node<int> listHead)
        {
            var resultHead = new Node<int>(0, listHead);
            var prevNode = resultHead;
            var currentNode = listHead;

            currentNode = currentNode.GetNext();
            while (currentNode != null)
            {
                Node<int> nextNode = currentNode.GetNext();
                int counter = 1;
                while (nextNode != null && currentNode.GetValue() == nextNode.GetValue())
                {
                    counter++;
                    nextNode = nextNode.GetNext();
                }
                if (counter >= 3){prevNode.SetNext(nextNode);}

                else {prevNode = currentNode;}

                currentNode = nextNode;

                currentNode = currentNode.GetNext(); //If nodes get deleted it goes straight to the place after deletion, if not it goes the the place after checking the duplicates.
            }
            return listHead;
        }

i really hope this works cuz i gotta go sleep its 2:30 am doesnt workkkk mannnnn i needs go to sleep i got school in 5 hours Thank you so mcuh for the help i really really really appreciate it ill go over this tmrw again tysm good night

Accord•13mo ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ Removing dupes in a linked list