数据结构-2、两种方法逆转单项链表（C#实现）

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

namespace ReverseNode
{
    class Program
    {
        static void Main(string[] args)
        {
            LinkList<int> TestNodeLink = new LinkList<int>();
            TestNodeLink.AddLinkNode(1);
            TestNodeLink.AddLinkNode(2);
            TestNodeLink.AddLinkNode(3);
            TestNodeLink.AddLinkNode(4);
            TestNodeLink.AddLinkNode(5);
            TestNodeLink.AddLinkNode(6);
            TestNodeLink.AddLinkNode(7);
            
            //TestNodeLink.Reverse2(TestNodeLink);
            TestNodeLink.PrintAllNodes();
            Console.WriteLine("使用递归反转后：");

            //LinkNode = new LinkNode<int>();
            LinkNode<int> pre = null;
            LinkNode<int> current = TestNodeLink.Head.Next;
            Console.WriteLine("current = {0}", current.Data);
            LinkNode<int> next = current.Next;
            TestNodeLink.Reverse1(pre, current, next);
            if (TestNodeLink.Head == null)
            {
                Console.WriteLine("TestNodeLink.Head == null");
            }
            TestNodeLink.PrintAllNodes();

            Console.ReadKey();
        }
    }

    public class LinkNode<T>
    {
        public T Data { get; set; }
        public LinkNode<T> Next { get; set; }
        public LinkNode(T data)
        {
            Data = data;
            Next = null;
        }
        public LinkNode()
        {
            Next = null;
        }
    }

    public class LinkList<T>
    {
        //构造函数
        public LinkList()
        {
            Head = new LinkNode<T>();
        }
        public LinkNode<T> Head;//表头
        
        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;
            }
        }

        //方法一：递归实现反转
        public LinkNode<T> Reverse1(LinkNode<T> node1Pre, LinkNode<T> node2Current, LinkNode<T> node3Next)
        {
            node2Current.Next = node1Pre;
            if (node3Next == null)
            {
                Console.WriteLine("返回，表头node2Current = {0}", node2Current.Data);
                Head = node2Current;
                return node2Current;
            }
            else
            {
                Reverse1(node2Current, node3Next, node3Next.Next);
            }
            return null;
        }

        //方法二:遍历交换
        public LinkList<T> Reverse2(LinkList<T> link)
        {
            if (link.Head == null || link.Head.Next == null)
            {
                return link;
            }

            LinkNode<T> head = null;
            LinkNode<T> current = null;//当前节点的指针
            LinkNode<T> pre = null;

            head = link.Head;
            current = link.Head;

            while(current != null)
            {
                //1、临时存储
                LinkNode<T> nextTemp = current.Next;
                //2、切断(链头)或指向前节点
                current.Next = pre;
                //3、更新pre
                pre = current;
                //4、更新current
                current = nextTemp;
            }

            link.Head = pre;
            return link;
        }
    }

}