DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Aniruddha has posted 40 posts at DZone. View Full User Profile

Sort Linked List in Ascending Order - C#

06.04.2012
| 10688 views |
  • submit to reddit
/// <summary>
        /// This method sorts elements in linked list and returns a new sorted linked list
        /// </summary>
        /// <param name="head">head node of unsorted linked list</param>
        /// <param name="count">number of elements in unsorted linked list</param>
        /// <returns>head node of new sorted linked list</returns>
        public static Node SortLinkedList(Node head, int count)
        {
            // Basic Algorithm Steps
            //1. Find Min Node
            //2. Remove Min Node and attach it to new Sorted linked list
            //3. Repeat "count" number of times

            Node _current = head;
            Node _previous = _current;

            Node _min = _current;
            Node _minPrevious = _min;

            Node _sortedListHead = null;
            Node _sortedListTail = _sortedListHead;

            for (int i = 0; i < count; i++)
            {
                _current = head;
                _min = _current;
                _minPrevious = _min;

                //Find min Node
                while (_current != null)
                {
                    if (_current.Data < _min.Data)
                    {
                        _min = _current;
                        _minPrevious = _previous;
                    }
                    _previous = _current;
                    _current = _current.Next;
                }

                // Remove min Node 
                if (_min == head)
                {
                    head = head.Next;
                }
                else if (_min.Next == null) //if tail is min node
                {
                    _minPrevious.Next = null;
                }
                else
                {
                    _minPrevious.Next = _minPrevious.Next.Next;
                }


                //Attach min Node to the new sorted linked list
                if (_sortedListHead != null)
                {
                    _sortedListTail.Next = _min;
                    _sortedListTail = _sortedListTail.Next;
                }
                else
                {
                    _sortedListHead = _min;
                    _sortedListTail = _sortedListHead;
                }
            }

            return _sortedListHead;
        }

Sort Linked List in Ascending Order - C#

Efficiency: O(n^2)

Inspired by Selection Sort algorithm