问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3828 访问。
反转一个单链表。
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
Reverse a singly linked list.
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3828 访问。
public class Program {
public static void Main(string[] args) {
var head = new ListNode(1) {
next = new ListNode(2) {
next = new ListNode(3) {
next = new ListNode(4) {
next = new ListNode(5)
}
}
}
};
var res = ReverseList(head);
ShowArray(res);
head = new ListNode(10) {
next = new ListNode(7) {
next = new ListNode(23) {
next = new ListNode(86) {
next = new ListNode(56)
}
}
}
};
res = ReverseList2(head);
ShowArray(res);
Console.ReadKey();
}
private static void ShowArray(ListNode list) {
var node = list;
while(node != null) {
Console.Write($"{node.val} ");
node = node.next;
}
Console.WriteLine();
}
private static ListNode ReverseList(ListNode head) {
var node = head;
ListNode pre = null;
while(node != null) {
var temp = node.next;
node.next = pre;
pre = node;
node = temp;
}
return pre;
}
private static ListNode ReverseList2(ListNode head) {
if(head == null || head.next == null) return head;
var result = ReverseList2(head.next);
head.next.next = head;
head.next = null;
return result;
}
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
}以上给出2种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/3828 访问。
5 4 3 2 1
56 86 23 7 10分析：
显而易见，以上2种算法的时间复杂度均为： 。