Success is stumbling from failure to failure with no loss of enthusiasm.
成功是在失败中摸索,同时不失去热情。
问题描述
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
限制:
0 <= 节点个数 <= 5000
使用栈解决
链表的反转是老生常谈的一个问题了,同时也是面试中常考的一道题。最简单的一种方式就是使用栈,因为栈是先进后出的。实现原理就是把链表节点一个个入栈,当全部入栈完之后再一个个出栈,出栈的时候在把出栈的结点串成一个新的链表。原理如下
代码比较简单,来看下
1public ListNode reverseList(ListNode head) { 2 Stack<ListNode> stack = new Stack<>(); 3 //把链表节点全部摘掉放到栈中 4 while (head != null) { 5 stack.push(head); 6 head = head.next; 7 } 8 if (stack.isEmpty()) 9 return null;10 ListNode node = stack.pop();11 ListNode dummy = node;12 //栈中的结点全部出栈,然后重新连成一个新的链表13 while (!stack.isEmpty()) {14 ListNode tempNode = stack.pop();15 node.next = tempNode;16 node = node.next;17 }18 //最后一个结点就是反转前的头结点,一定要让他的next19 //等于空,否则会构成环20 node.next = null;21 return dummy;22}
双链表求解
双链表求解是把原链表的结点一个个摘掉,每次摘掉的链表都让他成为新的链表的头结点,然后更新新链表。下面以链表1→2→3→4为例画个图来看下。
他每次访问的原链表节点都会成为新链表的头结点,最后再来看下代码
1public ListNode reverseList(ListNode head) { 2 //新链表 3 ListNode newHead = null; 4 while (head != null) { 5 //先保存访问的节点的下一个节点,保存起来 6 //留着下一步访问的 7 ListNode temp = head.next; 8 //每次访问的原链表节点都会成为新链表的头结点, 9 //其实就是把新链表挂到访问的原链表节点的10 //后面就行了11 head.next = newHead;12 //更新新链表13 newHead = head;14 //重新赋值,继续访问15 head = temp;16 }17 //返回新链表18 return newHead;19}
递归解决
我们再来回顾一下递归的模板,终止条件,递归调用,逻辑处理。
1public ListNode reverseList(参数0) { 2 if (终止条件) 3 return; 4 5 逻辑处理(可能有,也可能没有,具体问题具体分析) 6 7 //递归调用 8 ListNode reverse = reverseList(参数1); 910 逻辑处理(可能有,也可能没有,具体问题具体分析)11}
终止条件就是链表为空,或者是链表没有尾结点的时候,直接返回
if (head == null || head.next == null)
递归调用是要从当前节点的下一个结点开始递归。逻辑处理这块是要把当前节点挂到递归之后的链表的末尾,看下代码
1public ListNode reverseList(ListNode head) { 2 //终止条件 3 if (head == null || head.next == null) 4 return head; 5 //保存当前节点的下一个结点 6 ListNode next = head.next; 7 //从当前节点的下一个结点开始递归调用 8 ListNode reverse = reverseList(next); 9 //reverse是反转之后的链表,因为函数reverseList10 // 表示的是对链表的反转,所以反转完之后next肯定11 // 是链表reverse的尾结点,然后我们再把当前节点12 //head挂到next节点的后面就完成了链表的反转。13 next.next = head;14 //这里head相当于变成了尾结点,尾结点都是为空的,15 //否则会构成环16 head.next = null;17 return reverse;18}
因为递归调用之后head.next节点就会成为reverse节点的尾结点,我们可以直接让head.next.next = head;,这样代码会更简洁一些,看下代码
1public ListNode reverseList(ListNode head) {2 if (head == null || head.next == null)3 return head;4 ListNode reverse = reverseList(head.next);5 head.next.next = head;6 head.next = null;7 return reverse;8}
这种递归往下传递的时候基本上没有逻辑处理,当往回反弹的时候才开始处理,也就是从链表的尾端往前开始处理的。我们还可以再来改一下,在链表递归的时候从前往后处理,处理完之后直接返回递归的结果,这就是所谓的尾递归,这种运行效率要比上一种好很多
1public ListNode reverseList(ListNode head) { 2 return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6 if (head == null) 7 return newHead; 8 ListNode next = head.next; 9 head.next = newHead;10 return reverseListInt(next, head);11}
尾递归虽然也会不停的压栈,但由于最后返回的是递归函数的值,所以在返回的时候都会一次性出栈,不会一个个出栈这么慢。但如果我们再来改一下,像下面代码这样又会一个个出栈了
1public ListNode reverseList(ListNode head) { 2 return reverseListInt(head, null); 3} 4 5private ListNode reverseListInt(ListNode head, ListNode newHead) { 6 if (head == null) 7 return newHead; 8 ListNode next = head.next; 9 head.next = newHead;10 ListNode node = reverseListInt(next, head);11 return node;12}
总结
链表反转使用栈虽然也能实现,但一般不是很推荐,下面两种实现方式会好一些。使用栈能实现链表的反转,那么使用队列呢,如果使用双端队列也是可以的,从一端全部入队,然后再从这一端全部出队,说了半天这不还是和栈一样吗……
长按上图,识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧
本文分享自微信公众号 - 数据结构和算法(sjjghsf)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。