Half/split a linked list in such a fashion.
I am trying to split a singly linked list called "unsorted" into two lists left and right in such fashion that the odd nodes in "unsorted" will go to left and the even ones will go to right. After that, I want to delete those nodes in "unsorted", and I now have two separate lists: left and right.
Code:
if(unsorted == null || unsorted.next == null)
{
return unsorted;
}
else {
Node temp = unsorted.next.next;
Node left = unsorted;
Node right = unsorted.next;
left.next = null;
right.next = null;
unsorted = temp;
while (temp.next != null) {
left.next = temp;
right.next = temp.next;
left.next.next = null;
right.next.next = null;
temp = temp.next.next;
unsorted = temp;
}
}
I think I am stuck at my logics in the while loop. Before the while loop, I extract the first two nodes in the unsorted list and then delete them. The first the time the loop runs, I can extract the next two nodes in the unsorted list. But for the second time run, is left.next still pointing at the third node in the unsorted list? (Well, I already deleted the first two nodes but for the sake of my description, I need to say the third node so it is easy to describe my logics) If so, I did not successfully update my left and right linked lists, correct? Please give me some hints how to correctly update my left and right lists. Thank you.
Re: Half/split a linked list in such a fashion.
