[数据结构与算法]leetcode206-反转链表

一.题目描述

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
输入：head = [1,2]
输出：[2,1]
输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

二.题目解析

1.递归法

public ListNode reverseList1(ListNode head) {
        /*递归方式，递推公式reverseList的含义是：把拿到的链表进行反转，然后返回新的头结点。
         * */
        //判断链表为空或者只有一个元素 || 递归终止条件
        if(head == null || head.next == null){
            return head;
        }
        //返回当前元素后面所有节点反转后的头结点（是固定的）
        ListNode leftHead = reverseList(head.next);
        //2 -->  3<--4   =>  2.next.next = 2 即实现了反转
        head.next.next = head;
        //head置为空返回到上一层递归调用会被重新赋值（head.next.next = head）
        head.next = null;
        //每层调用返回的leftHead是一样的
        return leftHead;

    }

2.双指针迭代遍历

 public ListNode reverseList(ListNode head) {
        /*迭代方式
        * */
        //判断链表为空或者只有一个元素
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode nextPre = new ListNode();
        ListNode nextCur = new ListNode();
        while(cur != null){
            //由于后边cur指向会发生变化，先备份nextPre和nextCur
            nextCur = cur.next;
            cur.next = pre;
            if(pre == head){
                pre.next = null;
            }
            //更新指针
            pre = cur;
            cur = nextCur;
        }
        //最终的pre指向就是反转后的头结点
        return pre;

    }

这里还可以优化一下，不需要单独考虑头结点
令pre初始值为null，cur初始值是头结点即可

public ListNode reverseList(ListNode head) {
        /*迭代方式
        * */
        //判断链表为空或者只有一个元素
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode nextPre = new ListNode();
        ListNode nextCur = new ListNode();
        while(cur != null){
            //由于后边cur指向会发生变化，先备份nextCur
            nextCur = cur.next;
            cur.next = pre;
            //更新指针
            pre = cur;
            cur = nextCur;
        }
        //最终的pre指向就是反转后的头结点
        return pre;

    }