单链表逆序（c#版）

昨天园子里的老赵给我出一道题，比较有意思，在这里和大家分享一下。
要求如下：
有一个单向链表，你获得了它的头节点引用，用空间复杂度为O(1)的算法，将其逆序
空间复杂度为O(1)表示你可以声明单个变量，但是不能创建一个数组等集合类型

首先构建结点

 1    /**//// <summary>
 2    /// 结点类
 3    /// 为方便起见，结点数据类型用int表示
 4    /// </summary>
 5    public class ListNode
 6    {
 7        public int data; 
 8       
 9        public ListNode next;
10    }

为了方便大家看我就不把单链表的所有实现代码都copy上了。因为网上单链表的实现c#版的已经很多了。但是我百度了一下逆序c#版的逆序还没有，这也是我为什么放在这里的原因。不多说了。看代码：

 1    public class LinkList
 2    {
 3        private ListNode first;   //第一个结点
 4        public LinkList()
 5        {
 6            first = null;
 7        }
 8
 9        public bool IsEmpty()
10        {
11            return first == null;
12        }
13
14
15        /**//// <summary>
16        /// 逆序
17        /// </summary>
18        /// <returns></returns>
19        public void Reversion()
20        {
21            if (first == null)
22                new Exception("Empty");
23
24            ListNode current = null;
25            ListNode temp;
26
27            while (first != null)
28            {
29                temp = new ListNode();//构建新的结点
30                temp.data = first.data;//对结点数据进行复制
31                temp.next = current;
32                current = temp;
33                first = first.next;
34            }
35            first = current;
36
37        }
38
39
40        /**//// <summary>
41        /// 在第k个元素之后插入x
42        /// </summary>
43        /// <param name="k"></param>
44        /// <param name="x"></param>
45        /// <returns></returns>
46        public LinkList Insert(int k, int x)
47        {
48            //如果不存在第k个元素,则引发异常OutOfBoundsException
49            if (k < 0)
50                throw (new Exception(" OutOfBoundsException()"));
51                
52            ListNode pNode = first;  //pNode将最终指向第k个结点
53            for (int index = 1; index < k && pNode != null; index++)
54                pNode = pNode.next;
55            if (k > 0 && pNode == null)
56                throw (new Exception(" OutOfBoundsException()"));//不存在第k个元素
57            ListNode xNode = new ListNode();
58            xNode.data = x;
59            if (k > 0)
60            {
61                //在pNode之后插入
62                xNode.next = pNode.next;
63                pNode.next = xNode;
64            }
65            else
66            {
67                //作为第一个元素插入
68                xNode.next = first;
69                first = xNode;
70            }
71            return this;
72        }
73
74        public void Clear()
75        {
76            first = null;
77        }
78
79        public void OutPut()
80        {
81            ListNode current;
82            for (current = first; current != null; current = current.next)
83            {
84                Console.Write("{0}", current.data.ToString());
85            }
86
87            Console.WriteLine();
88        }
89    }

ok，可以看到我就实现了一些基本的构建单链表的方法，看看我们的主程序

 1        static void Main(string[] args)
 2        {
 3
 4            LinkList list = new LinkList();
 5            for (int i = 0; i < 100; i++)
 6            {
 7                list.Insert(i, i);
 8            }
 9            list.OutPut();
10
11            list.Reversion();
12
13            list.OutPut();
14
15            Console.ReadLine();
16        }

加下来测试一些，把i的上限改变一下1，2，3......
ok，通过！