南山做网站关于枪,建设网站的目标,电子商务网站建设预算表,seo优化个人博客给你单链表的头节点 head #xff0c;请你反转链表#xff0c;并返回反转后的链表。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5]
输出#xff1a;[5,4,3,2,1]示例 2#xff1a; 输入#xff1a;head [1,2]
输出#xff1a;[2,1]示例 3#xff1a;
输入请你反转链表并返回反转后的链表。 示例 1 输入head [1,2,3,4,5]
输出[5,4,3,2,1]示例 2 输入head [1,2]
输出[2,1]示例 3
输入head []
输出[]提示
链表中节点的数目范围是 [0, 5000]-5000 Node.val 5000 进阶链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题
思路
如果再定义一个新的链表实现链表元素的反转其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向直接将链表反转 而不用重新定义一个新的链表如图所示: 之前链表的头节点是元素1 反转之后头结点就是元素5 这里并没有添加或者删除节点仅仅是改变next指针的方向。
那么接下来看一看是如何反转的呢
我们拿有示例中的链表来举例 首先定义一个cur指针指向头结点再定义一个pre指针初始化为null。
然后就要开始反转了首先要把 cur-next 节点用tmp指针保存一下也就是保存一下这个节点。
为什么要保存一下这个节点呢因为接下来要改变 cur-next 的指向了将cur-next 指向pre 此时已经反转了第一个节点了。
接下来就是循环走如下代码逻辑了继续移动pre和cur指针。
最后cur 指针已经指向了null循环结束链表也反转完毕了。 此时我们return pre指针就可以了pre指针就指向了新的头结点。 Java
// 双指针
class Solution {public ListNode reverseList(ListNode head) {ListNode prev null;ListNode cur head;ListNode temp null;while (cur ! null) {temp cur.next;// 保存下一个节点cur.next prev;prev cur;cur temp;}return prev;}
}// 递归
class Solution {public ListNode reverseList(ListNode head) {return reverse(null, head);}private ListNode reverse(ListNode prev, ListNode cur) {if (cur null) {return prev;}ListNode temp null;temp cur.next;// 先保存下一个节点cur.next prev;// 反转// 更新prev、cur位置// prev cur;// cur temp;return reverse(cur, temp);}
}// 从后向前递归
class Solution {ListNode reverseList(ListNode head) {// 边缘条件判断if(head null) return null;if (head.next null) return head;// 递归调用翻转第二个节点开始往后的链表ListNode last reverseList(head.next);// 翻转头节点与第二个节点的指向head.next.next head;// 此时的 head 节点为尾节点next 需要指向 NULLhead.next null;return last;}
}使用虚拟头结点解决链表翻转 使用虚拟头结点通过头插法实现链表的翻转不需要栈 // 迭代方法增加虚头结点使用头插法实现链表翻转
public static ListNode reverseList1(ListNode head) {// 创建虚头结点ListNode dumpyHead new ListNode(-1);dumpyHead.next null;// 遍历所有节点ListNode cur head;while(cur ! null){ListNode temp cur.next;// 头插法cur.next dumpyHead.next;dumpyHead.next cur;cur temp;}return dumpyHead.next;
}使用栈解决反转链表的问题
首先将所有的结点入栈然后创建一个虚拟虚拟头结点让cur指向虚拟头结点。然后开始循环出栈每出来一个元素就把它加入到以虚拟头结点为头结点的链表当中最后返回即可。
public ListNode reverseList(ListNode head) {// 如果链表为空则返回空if (head null) return null;// 如果链表中只有只有一个元素则直接返回if (head.next null) return head;// 创建栈 每一个结点都入栈StackListNode stack new Stack();ListNode cur head;while (cur ! null) {stack.push(cur);cur cur.next;}// 创建一个虚拟头结点ListNode pHead new ListNode(0);cur pHead;while (!stack.isEmpty()) {ListNode node stack.pop();cur.next node;cur cur.next;}// 最后一个元素的next要赋值为空cur.next null;return pHead.next;
}采用这种方法需要注意一点。就是当整个出栈循环结束以后cur正好指向原来链表的第一个结点而此时结点1中的next指向的是结点2因此最后还需要cur.next null
