反转链表

题目：

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

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

思考：

提示

• 方法一：双指针迭代修改 next 指向

  • 让当前结点指向头结点，当前结点的前一个节点初始为空

  • 当前结点不等于 null 时，循环遍历链表

  • 循环中改变 next 指针的指向

  • 注意：在修改 next 指针指向时，先要临时保存当前的下一个结点，防止链表丢失

题解：

public ListNode reverseList(ListNode head) {

    ListNode cur = head, pre = null;

    while(cur != null) {
        ListNode tmp = cur.next; // 临时存放cur.next
        cur.next = pre;
        pre = cur;
        cur = tmp;
    }
    return pre;
}

提示

• 方法二：利用递归回溯修改 next 指向

  • 递归终止条件：当前结点为空返回

  • 递归：一直递归到最后一个不为 null 的节点，然后开始回溯修改 next 指向

题解：

public ListNode reverseList(ListNode head) {
    return recur(head, null);
}

private ListNode recur(ListNode cur, ListNode pre) {

  if (cur == null) return pre;

   ListNode res = recur(cur.next, cur); //递归调用
   cur.next = pre;  // 修改节点引用指向
   return res;
}