链表逆序补充

节点的表示

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace reverseListTest

{

    class ListNode

    {

        //节点的数据域

        public object val;

        //节点的指针域

        public ListNode next;

        /// <summary>

        /// 节点数据域赋值，指针域暂无指向

        /// </summary>

        /// <param name="x"></param>

        public ListNode(object x)

        {

            //指针没有指向，末尾

            next = null;

            val = x;

        }

        /// <summary>

        /// 空表

        /// </summary>

        public ListNode()

        {

            next = null;

            val = null;

        }

    }

}

链表的逆序和主程序

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace reverseListTest

{

    class Program

    {

        /// <summary>

        /// 链表逆序  递归

        /// 返回值是一个节点，是逆序链表之后的新头结点

        /// </summary>

        /// <param name="head"></param>

        /// <returns></returns>

        public static ListNode reverselist(ListNode head)

        {

            //如果头节点为空，或者头结点的下一个节点为空，直接返回头节点

            if (head == null)

            {

                return null;

            }

            if (head.next == null)

            {

                return head;

            }

            //此次递归时，链表的第二个节点

            //从链表的第二个节点开始子链表递归 

            ListNode second = head.next;

            //返回递归之后的新的头结点

            ////返回新的头结点，返回的是reverse好的新头节点

            ListNode newhead = reverselist(second);

            //处理老头结点和 上次递归时second的关系

            //重建老的头结点head和第二个节点second之间的关系。

            //因为reverlist(second)就把second之后的节点个逆序了

            //现在就是head和second节点没有逆序了

            head.next = null;

            second.next = head;

            return newhead;

        }

        /// <summary>

        /// 逆序  非递归

        /// </summary>

        /// <param name="head"></param>

        /// <returns></returns>

        public static ListNode reverse(ListNode head)

        {

            if (head == null || head.next == null)

            {

                return head;

            }

            //头节点

            ListNode pre = head;

            //头结点的下一个节点

            ListNode p = head.next;

            pre.next = null;

            ListNode nxt;

            while (p != null)

            {

                //nxt为p的下一个节点。

                nxt = p.next;

                //p指向pre，指向反转了

                p.next = pre;

                //pre,he p都向后移动一位。

                pre = p;

                p = nxt;

            }

            return pre;

        }

        static void Main(string[] args)

        {

            // 新建一个链表的头部，空表头

            ListNode head = new ListNode();

            //现在也就是p也是空表头，

            //因为head要一直保持在这里，作其他用途。

            //这p是head的copy，移动p也就是移动头结点

            //移动p之后，head仍是头结点，供下次使用。

            //移动p之后，p就在是头结点的备胎了。

            ListNode p = head;

            

            /// 下面的几句代码也能创建一个链表。

            //ListNode second = new ListNode(5); ;

            //head.next = second;

            //ListNode third = new ListNode(3);

            //second.next = third;

            //ListNode fourth = new ListNode(4);

            //third.next = fourth;

            ///用循环创建链表，

            for (int i = 0; i < 10; i++)

            {

                //新建一个链表，sec，sec的数据值为i，指针域为空。

                ListNode sec = new ListNode(i) ;

                //当i=0的时候，p也就是头结点。

                //i=0;p指向了新建的sec链表的指针域，这样就把p和sec链接起来了

                p.next = sec;

                //p往后移了，

                p = p.next;//也即是i=0时，p现在也是sec

            }

            //这里新建一个节点，把头结点给node，

            //方便输出节点

            ListNode node = head;

            while (node != null)

            {

                Console.WriteLine(node.val);

                node = node.next;

            }

            //此时head是for循环建立链表的头结点

            //用一个节点来接受，逆序之后链表的头结点

            //递归调用

          //  ListNode newhead= reverselist(head);

            //非递归调用

            ListNode newhead = reverse(head);

            //逆序之后新链表的输出

            while (newhead != null)

            {

                Console.WriteLine(newhead.val);

                newhead = newhead.next;

            }

            Console.Read();

        }

       

        

    }

}