带头节点链表的就地逆置及C#的实现

问题分析

逆置就是使得表中得内容由原来的
(a1,a2,...,ai-1,ai,ai+1,...,an)变为
(an,an-1,...,ai+1,ai,ai-1,...,a1)

就地逆置就是不需要额外申请节点空间，只需要利用原有表中的节点空间

算法思路

用头插法完成

初始化

逆置链表L初始为空链表，指针p指向原表当前处理节点

头插法

依次取原链表中当前节点p，将其作为第一个结点插入到逆置链表L表头L->next=p，q为保存原链表当前节点的下一个处理位置q=p->next

算法描述

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<string> head = new Node<string>();
            Node<string> a1 = new Node<string>("a1");
            Node<string> a2 = new Node<string>("a2");
            Node<string> a3 = new Node<string>("a3");

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

            Node<string> p = head.Next; //记录原表第一个元素节点的地址
            head.Next = null;   //将头节点的next域置空
            while (p != null)   
            {
                Node<string> q = p.Next; //保存下一个处理节点
                
                //插入节点
                p.Next = head.Next; 
                head.Next = p;

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

        }
    }
}