如A->B->C->D->E
思路一:
先取出链表的最后一个E,然后将E作为新链表的头,
现在状态为
原始链表:A->B->C->D
新链表:E
再取出原来链表的最后一个D,然后将D插入到新链表的最后位置,
现在状态为
原始链表:A->B->C
新链表:E->D
依次类推,最后形成E->D->C->B->A
很显然,这个算法的复杂度为O(n2)。
思路二:
取出原始链表的第一个节点A,然后将该节点作为新链表的头节点。
现在状态为
原始链表:B->C->D->E
新链表:A
然后同上,变为了下面的状态
原始链表:C->D->E
新链表:B->A
原始链表:D->E
新链表:C->B->A
原始链表:E
新链表:D->C->B->A
原始链表:
新链表:E->D->C->B->A
思路三:递归
http://blog.csdn.net/gykimo/article/details/8287746