剑指 Offer 24. 反转链表 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 限制： 0 <= 节点个数 <= 5000
1.迭代：
// 1.双指针迭代(方法中循环遍历，比如for/while) public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; ListNode next = null; while (cur !=null) { // 记录了cur.next的位置 next = cur.next; // 反转指针位置 cur.next = pre; // pre、cur指针移动一次 pre = cur; // pre移动到原来cur的位置 cur = next; // cur移动到原来cur.next的位置 } return pre; }
2.递归
// 2.递归 public ListNode reverseList1(ListNode head) { // 1).用此递归到最后5，停止递归 // 2).递归返回到1时，上一轮设置了1的next为null，停止递归 if (head==null || head.next==null) { return head; } // cur为递归到最后的一个节点，如1-2-3-4-5-null，停止递归后返回5 ListNode cur = reverseList1(head.next); // 5之后返回上层的递归，此时head为4 // head.next为5，head.next.next为5的下个节点 = 4 head.next.next = head; // 将4节点原来的next置空，免得4下节点到5，而5刚才赋到4成为循环链表 head.next = null; return cur; }
