
问题
反转一个单链表。
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
Reverse a singly linked list.
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
示例
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种算法实现,以下是这个案例的输出结果:
5 4 3 2 1 56 86 23 7 10
分析:
显而易见,以上2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3828。