链表分割及C#实现

问题分析

已知一个带头节点的单链表L，将比首节点大的放在首节点前面，否则放在首节点后面

算法描述

Node类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkReverse
{
    class Node<T>
    {
        private T data; //数据域
        private Node<T> next;  //引用域

        public T Data { get => data; set => data = value; }
        internal Node<T> Next { get => next; set => next = value; }

        /// <summary>
        /// 构造器
        /// </summary>
        public Node()
        {
            Data = default(T);
            Next = null;
        }

        /// <summary>
        /// 构造器
        /// </summary>
        /// <param name="data"></param>
        public Node(T data)
        {
            this.Data = data;
        }
    }
}

Program

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LinkReverse
{
    class Program
    {
        static void Main(string[] args)
        {
            Node<int> head = new Node<int>();
            Node<int> a1 = new Node<int>(3);
            Node<int> a2 = new Node<int>(2);
            Node<int> a3 = new Node<int>(1);
            Node<int> a4 = new Node<int>(4);
            Node<int> a5 = new Node<int>(5);

            head.Next = a1;
            a1.Next = a2;
            a2.Next = a3;
            a3.Next = a4;
            a4.Next = a5;

            Node<int> p = head.Next; //记录原表第一个元素节点的地址
            //拷贝首节点的值
            Node<int> h = new Node<int>();
            h.Data = p.Data;

            head.Next = null;   //将头节点的next域置空
            while (p.Next != null)
            {
                Node<int> q = p.Next; //保存下一个处理节点

                if (h.Data > p.Data)
                {
                    //插入节点后
                    p.Next = head.Next.Next;
                    head.Next.Next = p;
                }
                else
                {
                    //插入节点后
                    p.Next = head.Next;
                    head.Next = p;
                }

                p = q;
            }

            //遍历
            while (head.Next != null)
            {
                head = head.Next;
                Console.WriteLine(head.Data);
            }
        }
    }
}