每天一算法:「链表」反转链表 反转链表leetcode

点击上方"java全栈技术"关注我们，每天学习一个java知识点

小编最近整理了一些经典面试题目清单，将帮助您掌握算法及数据结构，并提高您的编程能力。

编程能力就像任何其他技能一样，也是一个可以通过刻意练习提高的。

大多数经典面试题目都有多种解决方案。 为了达到最佳的练习效果，强烈建议您至少将题目练习两遍，如果可以的话，三遍会更好。

刻意练习并不意味着寻找答案并记住它，这种练习方法不是长久之计。 在没有参考答案情况下，越能自主解决问题，才越能提高自身能力。

题目：通过率40.2% 难度：简单

描述：

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

代码模板

解题思路：

通过遍历时直接将指针反转，这样比较高效，但是需要处理好前后指针及后续的关系

迭代代码：

源代码：

class Solution {

public ListNode reverseList(ListNode head) {

ListNode prev = null;

while (head != null) {

ListNode temp = head.next;

head.next = prev;

prev = head;

head = temp;

}

return prev;

}

}

递归代码（非本人写亲测可通过）：

源代码：

class Solution {

public ListNode reverseList(ListNode head) {

return reverseListRecursively(head, null);

}

public ListNode reverseListRecursively(ListNode head, ListNode pre) {

if(head == null) {//当前节点为空，则直接返回指向前一节点的指针

return pre;

}

ListNode next = head.next;//备份当前节点的next指针

head.next = pre;//将当前节点的next指针指向前一节点

return reverseListRecursively(next, head);//递归调用方法，此时当前节点为原当前节点的 下一个节点，而前一节点为原当前节点

}

}

运行结果：