数据结构与算法-006-链表-反转单链表

反转链表，本题核心要点：搞明白如何做局部翻转，另外需要动手画图来操作加深理解

空间法，来自题解评论区-触不可及

// 该解法写的很简洁，空间、时间复杂度均为O(n)，非最优解，用来学习还不错

public ListNode reverseList(ListNode head) {
    ListNode ans = null;
    for (ListNode x = head; x != null; x = x.next) {
            ans = new ListNode(x.val,ans);
    }
    return ans;
}

迭代法，参考

    public ListNode reverseList(ListNode head) {
	// 迭代法，时间复杂度O(n)
        // 核心要点：需要厘清厘清交换逻辑
        ListNode curr=head;
        ListNode pre=null;
        // 当前节点为空时说明走到了最后一个节点
        while(curr!=null){
            // 保存下一个节点
            ListNode next=curr.next;
            // 清除当前节点的next指向
            curr.next=pre;
            // 翻转节点存储当前节点
            pre=curr;
            // 当前节点指向开始保存的next节点
            curr=next;
        }
        return pre;
    }

递归法,参考

public ListNode reverseList(ListNode head) {
       // 递归法，时间复杂度O(n)
       // 核心要点：存储翻转的节点，局部翻转
       // 递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
       // 此后，每次函数在返回的过程中，让当前结点的next 结点的 next 节点指向当前节点。
       // 同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
       // 当递归函数全部出栈后，链表反转完成。
       if(head==null||head.next==null){
           return head;
       }
       ListNode ret=reverseList(head.next);
       head.next.next=head;
       head.next=null;
       return ret;
    }