刷题记录----反转链表（反转整个链表）

目录

题目描述：给定一个链表，反转并返回新的头节点

迭代：

两个指针，pre和cur，cur代替头节点遍历链表，过程中用next记录下cur.next

递归：

递归：从后往前反转

把head.next以后的节点看成一个节点

---

题目描述：给定一个链表，反转并返回新的头节点

迭代：

两个指针，pre和cur，cur代替头节点遍历链表，过程中用next记录下cur.next

ListNode reverse(ListNode head) {
    ListNode pre = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;//记录下一个节点
        cur.next = pre;//改变第一个节点的指向
        pre = cur;//前驱节点更新为当前节点
        cur = next;//向后更新节点

    }
    return pre;
}

递归：

 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);
    }

递归：从后往前反转

把head.next以后的节点看成一个节点

    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 需要指向 NULL
        head.next = null;
        return last;
    }