【面试题16】反转链表

【题目描述】

定义一个函数，输入一个的头结点，反转该链表并输出反转后的头结点。

【解决方案】

我的代码实现，仅供参考：

 1         public static ListNode ReverseList(ListNode head)
 2         {
 3             ListNode headReverse = null;
 4             ListNode prev = null;
 5             ListNode node = head;
 6 
 7             while (node != null)
 8             {
 9                 ListNode next = node.Next;
10 
11                 if (next == null)
12                 {
13                     headReverse = node;
14                 }
15 
16                 node.Next = prev;
17                 prev = node;
18                 node = next;
19             }
20 
21             return headReverse;
22         }

【本题扩展】

用递归实现同样的反转链表的功能。

我的代码实现：

 1         public static ListNode ReverseList(ListNode head)
 2         {
 3             if (head == null || head.Next == null)
 4             {
 5                 return head;
 6             }
 7             else
 8             {
 9                 ListNode newHead = ReverseList(head.Next);
10                 head.Next.Next = head;
11                 head.Next = null;
12                 return newHead;
13             }
14         }