题目
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
解法1：迭代法
解题思路
迭代法的解题思路并不复杂，遍历链表，将 next 节点取出，使之成为头节点，以此循环，知道 next 节点为 null。
这种反转链表的运用在很多题目中都会用到，比如判断是否回文链表时，将链表的前半部分反转，判断是否和链表的后半部分相等。代码
class Solution {
public ListNode reverseList(ListNode head) {
// new node
ListNode nn = null;
// new link
ListNode nl = null;
while (head != null) {
// 保存下一个节点
nn = head.next;
// 当前头节点成为新的反转链表的头节点
head.next = nl;
// 更新反转链表
nl = head;
// 头节点指向下一节点
head = nn;
}
return nl;
}
}
解法2：递归法
- 解题思路
递归法的思路不是很好理解，因此我画了一张图说明每个语句执行后 newHead 的变化。建议大家可以自己 Debug 看看。
leetcode206.jpg
- 代码
class Solution {
public static ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
// 成环了，因为newHead和head其实是同一个引用，所以head改变时，newHead也会受到影响
// 此时newHead为反转后的链表，并且跟着一个链表环
head.next.next = head;
// 将环断开，此时newHead为反转后的链表
head.next = null;
return newHead;
}
}
