I am trying to perform sorting on a linked list using merge sort algorithm, but my code is giving me stackoverflow error I don't know why it is so and how to deal with my code.
Here is my code which contains insert method that adds the element in the beginning of a linked list, find middle method which use slow and fast pointer method to find the middle of linkedlist and sort method that has mergesort method to divide the linkedlist from middle and mergelist method to merge the list..
I am getting StackOverflow error for this code.
using System;
using System.Collections.Generic;
namespace ConsoleApp1
{
public class LinkedListNode<T>
{
public T _data;
public LinkedListNode<T> _nextNodeAddress;
public LinkedListNode(T data)
{
this._data = data;
}
}
public class LinkedList<T>
{
public LinkedListNode<T> _head;
public int size;
public LinkedList()
{
this._head = null;
this.size = 0;
}
public void InsertNode(T data)
{
LinkedListNode<T> newNode = new LinkedListNode<T>(data);
newNode._nextNodeAddress = this._head;
this._head = newNode;
this.size ;
}
public void PrintList(LinkedListNode<T> head)
{
LinkedListNode<T> tempPointer = this._head;
while (tempPointer != null)
{
Console.Write("->{0}", tempPointer._data);
tempPointer = tempPointer._nextNodeAddress;
}
Console.WriteLine("");
}
public LinkedListNode<T> Center(LinkedListNode<T> head)
{
LinkedListNode<T> slowPointer = head;
LinkedListNode<T> fastPointer = head;
while (fastPointer != null
&& fastPointer._nextNodeAddress != null)
{
slowPointer = slowPointer._nextNodeAddress;
fastPointer = fastPointer._nextNodeAddress._nextNodeAddress;
}
return slowPointer;
}
public LinkedListNode<T> MergeList(
LinkedListNode<T> start,
LinkedListNode<T> end)
{
if (start == null) return end;
if (end == null) return start;
int data1 = Convert.ToInt32(start._data);
int data2 = Convert.ToInt32(end._data);
LinkedListNode<T> result;
if (data1 <= data2)
{
result = start;
result._nextNodeAddress = MergeList(start._nextNodeAddress, end);
}
else
{
result = end;
result._nextNodeAddress = MergeList(start, end._nextNodeAddress);
}
return result;
}
public LinkedListNode<T> MergeSort(LinkedListNode<T> head)
{
if (head._nextNodeAddress == null || head == null) return head;
LinkedListNode<T> middle = Center(head);
LinkedListNode<T> nextOfMiddle = middle._nextNodeAddress;
middle._nextNodeAddress = null;
LinkedListNode<T> left = MergeSort(head);
LinkedListNode<T> right = MergeSort(nextOfMiddle);
LinkedListNode<T> li = MergeList(left, right);
return li;
}
public void Sort(LinkedListNode<T> head)
{
MergeSort(head);
}
}
class Program
{
static void Main(string[] args)
{
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.InsertNode(1);
linkedList.InsertNode(31);
linkedList.InsertNode(24);
linkedList.InsertNode(2);
linkedList.InsertNode(3);
linkedList.PrintList(linkedList._head);
linkedList.Sort(linkedList._head);
linkedList.PrintList(linkedList._head);
}
}
}
CodePudding user response：
A few issues:
Centerwill return the second node when the list has just two nodes. This means that the list will be split after that "center", which will make that the left-side split-off is the original list -- still having two nodes! This is the cause of an endless recursion. So make sure thatCenterreturns the first node in that case. To achieve that, letfaststart at the second node instead of the first.There is no provision to assign the least node (after sorting) to the
_headmember. You can do this inSort: assign the node that comes from theMergeSortcall back to_head.The condition
head == nullshould be evaluated beforehead._nextNodeAddress == null, not the other way roundThe parameter of
PrintListis not used. Just remove it.The
Sortmethod should not have a parameter.
Here is the code after making those adaptations:
public class LinkedListNode<T>
{
public T _data;
public LinkedListNode<T> _nextNodeAddress;
public LinkedListNode(T data)
{
this._data = data;
}
}
public class LinkedList<T>
{
public LinkedListNode<T> _head;
public int size;
public LinkedList()
{
this._head = null;
this.size = 0;
}
public void InsertNode(T data)
{
LinkedListNode<T> newNode = new LinkedListNode<T>(data);
newNode._nextNodeAddress = this._head;
this._head = newNode;
this.size ;
}
public void PrintList()
{
LinkedListNode<T> tempPointer = this._head;
while (tempPointer != null)
{
Console.Write("->{0}", tempPointer._data);
tempPointer = tempPointer._nextNodeAddress;
}
Console.WriteLine("");
}
public LinkedListNode<T> Center(LinkedListNode<T> head)
{
LinkedListNode<T> slowPointer = head;
// Center should be found sooner
LinkedListNode<T> fastPointer = head._nextNodeAddress;
while (fastPointer != null && fastPointer._nextNodeAddress != null)
{
slowPointer = slowPointer._nextNodeAddress;
fastPointer = fastPointer._nextNodeAddress._nextNodeAddress;
}
return slowPointer;
}
public LinkedListNode<T> MergeList(LinkedListNode<T> start, LinkedListNode<T> end)
{
if (start == null) return end;
if (end == null) return start;
int data1 = Convert.ToInt32(start._data);
int data2 = Convert.ToInt32(end._data);
LinkedListNode<T> result;
if (data1 <= data2)
{
result = start;
result._nextNodeAddress = MergeList(start._nextNodeAddress, end);
}
else
{
result = end;
result._nextNodeAddress = MergeList(start, end._nextNodeAddress);
}
return result;
}
public LinkedListNode<T> MergeSort(LinkedListNode<T> head, int i)
{
// reverse condition
if (head == null || head._nextNodeAddress == null) return head;
LinkedListNode<T> middle = Center(head);
LinkedListNode<T> nextOfMiddle = middle._nextNodeAddress;
middle._nextNodeAddress = null;
LinkedListNode<T> left = MergeSort(head, i 1);
LinkedListNode<T> right = MergeSort(nextOfMiddle, i 1);
LinkedListNode<T> li = MergeList(left, right);
return li;
}
public void Sort() // Should have no argument
{
// Should capture the new head:
this._head = MergeSort(this._head, 0);
}
}
class Program
{
static void Main(string[] args)
{
LinkedList<int> linkedList = new LinkedList<int>();
linkedList.InsertNode(1);
linkedList.InsertNode(31);
linkedList.InsertNode(24);
linkedList.InsertNode(2);
linkedList.InsertNode(3);
linkedList.PrintList();
linkedList.Sort();
linkedList.PrintList();
}
}
CodePudding user response：
Consider a list with two items. MergeSort will call Center(head);. That will return the second of the two items. This item will have its _nextNodeAddress set to null, but it is the last item, so it is already null, and the list remains unchanged.
The next statement is MergeSort(head);, and since the list still contains the same two items, we will just do the same thing again.
You might fix this problem by ensuring Center returns the first item instead of the second in case the number of items are equal. But there might very well be other issues with this code.
Note that it is quite rare to implement your own sorting. Using any kind of linked list is possibly even more rare in the real world. So I hope you are doing this as a learning exercise, and not for production code. I would also suggest reading a bit about test driven development and unit tests, since that can help isolate simple problems like this. I would also suggest reading Eric Lipperts article on How to debug small programs.