LeetCode 92:反转链表

题目：

方式一：

方式二：

方式三：

代码示例：

package com.zy.leetcode.LeetCode_206;

/**
 * @Author: zy
 * @Date: 2024-12-22-13:34
 * @Description:
 * 反转链表 II
 * 给你单链表的头指针 head 和两个整数 left 和 right ，
 * 其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */
public class ListNode206 {

    private int val;
    private ListNode206 next;

    public ListNode206(int val, ListNode206 next) {
        this.val = val;
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode206{" + "val=" + val + ", next=" + next + '}';
    }

    public ListNode206 ListNodeReverseMethod1(ListNode206 o1) {
        ListNode206 n1 = null;
        ListNode206 p = o1;
        while (p != null) {
            n1 = new ListNode206(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    /**
     * 方法2
     * 与方法1类似，构造一个新链表，
     * 从旧链表头部移除节点，添加到新链表头部，完成后新链表即是倒序的，区别在于原题目未提供节点外层的容器类，这里提供一个，另外一个区别是并不去构造新节点
     * J
     *
     * @param
     */
    public ListNode206 ListNodeReverseMethod2(ListNode206 o1) {
        List n1 = new List(o1);
        List n2 = new List(null);
        while (true) {
            ListNode206 first = n1.removeFirst();
            if (first == null) {
                break;
            }
            n2.addFirst(first);
        }
        return n2.head;
    }

    static class List {
        ListNode206 head;

        public List(ListNode206 head) {
            this.head = head;
        }

        private void addFirst(ListNode206 first) {
            first.next = head;
            head = first;
        }

        private ListNode206 removeFirst() {
            ListNode206 node = head;
            if (node != null) {
                head = node.next;
            }
            return node;
        }
    }

    /**
     * 使用递归方式
     *
     * @param old
     * @return 1 2 3 4 5
     */
    private ListNode206 reverseMethod3(ListNode206 old) {
        if (old == null || old.next == null) {
            return old;
        }
        ListNode206 last = old.reverseMethod3(old.next);
        //将节点之间调换 5 -》 4
        old.next.next = old;
        old.next = null;  // 断掉旧节点的next，保证
        // 下次循环时，old是最后一个节点
        // 5 -》 4 -》 3 -》 2 -》 1  即是反转的结果
        return last;

    }

    /**
     * 方式四
     *
     * @param o1
     * @return
     */
    private ListNode206 reverseMetthod4(ListNode206 o1) {
        //特殊情况
        //1。空链表
        //2。本身就一个元素
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode206 o2 = o1.next;
        ListNode206 n1 = o1;
        while (o2 != null) {
            o1.next = o2.next;//2
            o2.next = n1;//3
            n1 = o2;//4
            o2 = o1.next;//5
        }
        return n1;

    }

    private ListNode206 reverseMetthod5(ListNode206 o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode206 n1 = null;
        while (o1 != null) {
            ListNode206 o2 = o1.next;
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;

    }

    public static void main(String[] args) {

    }
}