Splitting a double linked list in half and appending the first half.

I don't even have code to show, I just cannot figure out how to split a double linked list in half and stitch it back together at the end. I've done a bit of searching around and cant quite come up with an answer. (I suck at pointers) Any guidance would be appreciated.
closed account (SECMoG1T)
What does this phrase mean.
and stitch it back together at the end.  do you mean split and join the front part to the end of the second part... ? Or what does these simply mean ...at the end
Last edited on
Yes split the first half of the link list and append the first half to the end of last half creating a single link list again.

This is what my code is now.

http://pastebin.com/8As86Vw8
Last edited on
closed account (SECMoG1T)
Well your current function will need just a little correction and should be working fine.

1
2
3
4
5
6
Card* DeckSplit(Card* head, Card* tail)// this might leak your memory
{   
      for (int i = 0; i < Split; i++)          
      head = head->next;  
       head = tail;        return(head);     
 }


Let me give you an idea on how to keep track of all your nodes

1. Iterate to your point of split, "note it will be handy to create to temporal pointers"
temp_tail which will point to the point of split and temp_head to point to the point of split +1

2. reset temp_tail next pointer to nullptr and similarly reset temp_head pointer previous to nullptr.
Now we got two separated parts.

3. let's join them.
Reset the initial head previous pointer to point to the initial tail, similarly reset the tail next pointer to
point to the head. Wow we just rejoined them as you wished hehe.

4. Now that we got our list up again we need to reset the head and tail pointers so that it will be similar to
our initial list. Here just set the head pointer equal to temp_head and tail equal to temp_tail .... that's it
our list is good to go.
Last edited on
I'm not entirely sure I understand, this is what I have as of know from your instructions. Its currently giving me 28 cards from the initial order.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Card* DeckSplit(Card* head, Card* tail)
{
	for (int i = 0; i < Split; i++)
		head = head->next;
	
	Card* temp_tail = nullptr;
	Card* temp_head = nullptr;

	temp_tail = head;
	temp_head = head->next;
	temp_head->next = nullptr;
	temp_tail->previous = nullptr;
	head->previous = tail;
	tail->next = head;
	head = temp_head;
	tail = temp_tail;
		return(head);
	
}
closed account (SECMoG1T)
I noted one of my point was misleading but i just re-edited that plus am also giving you the code to make things clear.

Here is the code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Card* DeckSplit(Card* head, Card* tail)
{   
      Card* temp_tail=head;
      Card* temp_head=nullptr; 

      for (int i = 1; i < =Split; i++)          
      temp_tail = temp_tail->next;  

      temp_head=temp_tail-> next;
      
      temp_tail-> next=nullptr; 
      temp_head-> previous=nullptr; /// separating list into 2 parts

     head->previous=tail;
     tail-> next=head;/// appending the two parts

     head=temp_head;
     tail=temp_tail;/// resetting to original form

     return head;
}
Last edited on
Topic archived. No new replies allowed.