C# 链表反转

链表反转分这么两种情况，

一种是链表头节点始终前置，那这时候需要传一个头节点特有的标记；（简称：头不转）

HEAD->Test1->Test2->Test3->Test4

反转后：

HEAD->Test4->Test3->Test2->Test1

---

另一种是不管头节点，连同头节点一起反转。 （简称：头也转）

HEAD->Test1->Test2->Test3->Test4

反转后：

Test4->Test3->Test2->Test1->HEAD

---

不管转不转头，都有递归实现和非递归实现。

先看一下我的链表类。

    public class LinkNode<T>
    {
       public T Data { get; set; }
      // public LinkNode<T> prev { get; set; }
        public LinkNode<T> Next { get; set; }

        public LinkNode(T data)
        {
            this.Data = data;
            Next = null;
        }
        public LinkNode()
        {
            this.Next=null;
        }

    }

    public class LinkList<T>
    {
        public LinkNode<T> Head;
        public LinkList()
        {
            Head = new LinkNode<T>();
        }
        public void AddLinkNode(T valueToAdd)
        {
            var newNode = new LinkNode<T>(valueToAdd);
            LinkNode<T> tmp = Head;
            while (tmp.Next != null)
            {
                tmp = tmp.Next;
            }
            tmp.Next = newNode;


        }
        public void PrintAllNodes()
        {
            LinkNode<T> tmp = Head;
            while (tmp != null)
            {
                Console.WriteLine(tmp.Data);
                tmp = tmp.Next;
            }
        }
    }

好了，然后看一下

①头也转情况的递归实现：

        /// <summary>
        /// 头也转的递归实现
        /// </summary>
        /// <param name="node1"></param>
        /// <param name="node2"></param>
        /// <returns></returns>
        public LinkNode<T> ReverseRecursiveNohead(LinkNode<T> node1, LinkNode<T> node2)
        {
            bool head = false;
            if (node1 == this.Head) head = true;
            LinkNode<T> tmp = node2.Next;
            node2.Next = node1;
            if (head) node1.Next = null;
            if (tmp == null) {
                return node2; }
            else
            {
               return ReverseRecursiveNohead(node2, tmp);
            }
        }

main中调用

            var linklist = new LinkList<string>();
            Console.WriteLine("______原始链表打印________");
            linklist.Head.Data = "HEAD";
            linklist.AddLinkNode("test1");
            linklist.AddLinkNode("test2");
            linklist.AddLinkNode("test3");
            linklist.AddLinkNode("test4");
            linklist.PrintAllNodes();
            Console.WriteLine("______头也转的递归实现________");
            
            linklist.Head= linklist.ReverseRecursiveNohead(linklist.Head, linklist.Head.Next);
            linklist.PrintAllNodes();

效果：

②头也转情况的非递归实现：

/// <summary>
        /// 头也转的非递归实现
        /// </summary>
        /// <param name="head"></param>
        /// <returns></returns>
        public LinkNode<T> ReverseNonRecursive(LinkNode<T> head)
        {
            LinkNode<T> tmp1 = new LinkNode<T>(), tmp2 = new LinkNode<T>();
            while (head != null)
            {
                tmp2 = head.Next;//save next head
                head.Next = tmp1;
                tmp1 = head;
                head = tmp2;

            }
            return tmp1;

        }

main中调用

            var linklist = new LinkList<string>();
            Console.WriteLine("______原始链表打印________");
            linklist.Head.Data = "HEAD";
            linklist.AddLinkNode("test1");
            linklist.AddLinkNode("test2");
            linklist.AddLinkNode("test3");
            linklist.AddLinkNode("test4");
            linklist.PrintAllNodes();
            Console.WriteLine("_______头也转的非递归实现_______");
            linklist.Head = linklist.ReverseNonRecursive(linklist.Head);
            linklist.PrintAllNodes();

效果：

③头不转的递归实现：

/// <summary>
        /// 头结点不转，头始终是头的递归实现
        /// </summary>
        /// <param name="node1"></param>
        /// <param name="node2"></param>
        /// <param name="head"></param>
        /// <returns></returns>
        public LinkNode<T> ReverseRecurse(LinkNode<T> node1,LinkNode<T> node2,T head){
            if (node2 == null)
            {
                return null;
            }
            else
            {
                if (node2.Next == null)
                {
                    Head.Next = node2;
                    node2.Next = node1;
                    node1.Next = null;
                    return Head;
                }
                else
                {
                    ReverseRecurse(node2, node2.Next,head);
                    node2.Next = node1;
                    if (node2.Next.Data.Equals(head))
                    {
                        node2.Next = null;
                        return Head; 
                    }
                    node1.Next = null;
                    return Head;
                }
            }

        }

main中调用

            var linklist = new LinkList<string>();
            Console.WriteLine("______原始链表打印________");
            linklist.Head.Data = "HEAD";
            linklist.AddLinkNode("test1");
            linklist.AddLinkNode("test2");
            linklist.AddLinkNode("test3");
            linklist.AddLinkNode("test4");
            linklist.PrintAllNodes();

            Console.WriteLine("_______头不转的递归实现_______");
            linklist.ReverseRecurse(linklist.Head,linklist.Head.Next,"HEAD");
            linklist.PrintAllNodes();

效果：

 好像还差一种，大家自己发挥~