Insert a doubly linkedList in the middle of another-CodePudding

I'm trying to insert a doubly in the middle of another one(with an even amount of nodes). Everything works well until the middle list is finished and the second half of the original one is supposed to start. Can't figure out why (CountNodes returns an int with numbers on nodes in a list)


        //insert middleList in the middle of 'list'
        public static void insertInMiddle(BinNode<int> list, BinNode<int> middleList)
        {
            BinNode<int> pos = list;
            BinNode<int> posMid = middleList;
            for(int i = 0; i < CountNodes(list) /2 -1; i  )
            {
                pos = pos.GetRight();
            }
            pos.SetRight(posMid);
            posMid.SetLeft(pos);
            while (posMid.GetRight() != null)
            {            
                posMid = posMid.GetRight();
            }
            for (int i = 0; i < CountNodes(middleList); i  )
            {
                pos = pos.GetRight();
            }
            posMid.SetRight(pos);
            pos.SetLeft(posMid);
            
        }
        static void Main(string[] args)
        {
            //List in middle
            BinNode<int> p1 = new BinNode<int>(20);
            BinNode<int> p2 = new BinNode<int>(50);
            BinNode<int> p3 = new BinNode<int>(35);
            BinNode<int> p4 = new BinNode<int>(10);
            BinNode<int> p5 = new BinNode<int>(60);

            //Original list
            BinNode<int> c1 = new BinNode<int>(100);
            BinNode<int> c2 = new BinNode<int>(110);
            BinNode<int> c3 = new BinNode<int>(120);
            BinNode<int> c4 = new BinNode<int>(130);

            Add(p1,p2); Add(p2, p3); Add(p3, p4); Add(p4, p5); p5.SetRight(null);
            Add(c1, c2); Add(c2, c3); Add(c3, c4);

            insertInMiddle(c1, p1);
            Print(c1);

            Console.ReadKey();
        }

CodePudding user response：

If I am understanding your intent correctly, there seem to be a couple problems with the logic. You go to the middle of the first list correctly, but I think things break down after that, if I understand correctly, you want to do something like this, lets say list 1 is "1, 2, 3, 7, 8, 9" and list 2 is "4, 5, 6" you want the final list to be "1, 2, 3, 4, 5, 6, 7, 8, 9". This means that once you get halfway through list one you need to point that node ("3") to the first node of list 2 ("4", which you do) and the first node of list 2 ("4") to the mid point of list 1 ("3", also done), so far so good.

The problem is that the next step should be to point the last node of list 2 to the next node of list 1, but because you have already updated the "3" to point to "4" so you don't have a way to get to "7" anymore as calling GetRight() on "3" gets you to "4".

What you need is another variable that stores the next node in order for list 1 so that you can link the last node in list 2 back to it. In terms of my example, before calling SetRight on "3" you need to store the result of of calling GetRight() on "3" in a new variable and then set the last item in list 2 to point to this new variable.

Hope this helps.

CodePudding user response：

When pos.SetRight(posMid); is executed, any reference to the second half of the original list is lost as the only way to get there was via pos.GetRight(), but after this SetRight call, that reference has been overwritten with another.

So do like this:

public static void insertInMiddle(BinNode<int> list, BinNode<int> middleList)
{
    BinNode<int> pos = list;
    BinNode<int> posMid = middleList;
    for(int i = 0; i < CountNodes(list) /2 -1; i  )
    {
        pos = pos.GetRight();
    }
    BinNode<int> secondHalf = pos.getRight();  // Get a reference
    pos.SetRight(posMid);
    posMid.SetLeft(pos);
    while (posMid.GetRight() != null)
    {            
        posMid = posMid.GetRight();
    }
    // make the second link
    posMid.SetRight(secondHalf);
    secondHalf.SetLeft(posMid);   
}