算法学习---反转链表的两种方法(栈&递归)

内容目录

题目描述解法一：栈解法二：递归

题目描述

给出一个链表，返回链表的反转，例如

输入：1->2->3->4->5->null 输出：5->4->3->2->1->null

解法一：栈

这个做法是比较先想到的，栈的先进后出的特点能很好地帮助我们实现反转，步骤也比较简单，就是空间复杂度是O(n)，所以其实这种做法是不太好的

先遍历一遍链表，把每个结点压入到栈里去，创建一个新的结点，把栈里的每一个元素弹出来，放到结点后面 public ListNode reverse1(ListNode head){ //如果是空链表或是只有一个结点的链表，就没有反转的必要，直接返回 if (head==null || head.next==null) return head; Stack<ListNode> stack = new Stack<>(); //把所有结点压入栈 while (head!=null){ stack.push(head); head = head.next; } ListNode ans = new ListNode(0); //设置一个临时结点，用来把栈中的结点加入到链表中 ListNode temp = ans; while (!stack.isEmpty()){ temp.next = stack.pop(); temp = temp.next; } return ans.next; }

解法二：递归

其实主要是想记录一下递归的这种解法，因为有点绕，自己写一下的话肯定会加深一下印象 我们的初始状态是 要得到的结果是 递归要完成的工作是（就上图而言）：

5指向4，4指向null4指向3，3指向null重复如上动作最后2指向1，1指向null

看图示是不是更清楚了，代码如下

public ListNode reverse2(ListNode head){ if (head==null||head.next==null) return head; ListNode newHead = reverse2(head.next); //5指向4，后面同理 head.next.next = head; //4指向null，后面同理 head.next = null; return newHead; }

如果还不清楚的话，跟着代码自己敲一遍，应该就能理解了。